taking-maximum-energy-from-the-mystic-dungeon

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

In a mystic dungeon, <code>n</code> magicians are standing in a line. Each magician has an attribute that gives you energy. Some magicians can give you negative energy, which means taking energy from you.

You have been cursed in such a way that after absorbing energy from magician <code>i</code>, you will be instantly transported to magician <code>(i + k)</code>. This process will be repeated until you reach the magician where <code>(i + k)</code> does not exist.

In other words, you will choose a starting point and then teleport with <code>k</code> jumps until you reach the end of the magicians&#39; sequence, absorbing all the energy during the journey.

You are given an array <code>energy</code> and an integer <code>k</code>. Return the maximum possible energy you can gain.

Note that when you are reach a magician, you must take energy from them, whether it is negative or positive energy.

&nbsp;
Example 1:

<div class="example-block" style="
 border-color: var(--border-tertiary);
 border-left-width: 2px;
 color: var(--text-secondary);
 font-size: .875rem;
 margin-bottom: 1rem;
 margin-top: 1rem;
 overflow: visible;
 padding-left: 1rem;
">
Input: energy = [5,2,-10,-5,1], k = 3

Output: 3

Explanation: We can gain a total energy of 3 by starting from magician 1 absorbing 2 + 1 = 3.
</div>

Example 2:

<div class="example-block" style="
 border-color: var(--border-tertiary);
 border-left-width: 2px;
 color: var(--text-secondary);
 font-size: .875rem;
 margin-bottom: 1rem;
 margin-top: 1rem;
 overflow: visible;
 padding-left: 1rem;
">
Input: energy = [-2,-3,-1], k = 2

Output: -1

Explanation: We can gain a total energy of -1 by starting from magician 2.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= energy.length &lt;= 105</code></li>
	<li><code>-1000 &lt;= energy[i] &lt;= 1000</code></li>
	<li><code>1 &lt;= k &lt;= energy.length - 1</code></li>
</ul>

&nbsp;
​​​​​​

maximumEnergy

Taking Maximum Energy From the Mystic Dungeon

Array

Prefix Sum

在神秘的地牢中，<code>n</code> 个魔法师站成一排。每个魔法师都拥有一个属性，这个属性可以给你提供能量。有些魔法师可能会给你负能量，即从你身上吸取能量。

你被施加了一种诅咒，当你从魔法师 <code>i</code> 处吸收能量后，你将被立即传送到魔法师 <code>(i + k)</code> 处。这一过程将重复进行，直到你到达一个不存在 <code>(i + k)</code> 的魔法师为止。

换句话说，你将选择一个起点，然后以 <code>k</code> 为间隔跳跃，直到到达魔法师序列的末端，在过程中吸收所有的能量。

给定一个数组 <code>energy</code> 和一个整数<code>k</code>，返回你能获得的 最大 能量。

&nbsp;

示例 1：

<div class="example-block" style="
 border-color: var(--border-tertiary);
 border-left-width: 2px;
 color: var(--text-secondary);
 font-size: .875rem;
 margin-bottom: 1rem;
 margin-top: 1rem;
 overflow: visible;
 padding-left: 1rem;
">
输入： energy = [5,2,-10,-5,1], k = 3

输出： 3

解释：可以从魔法师 1 开始，吸收能量 2 + 1 = 3。
</div>

示例 2：

<div class="example-block" style="
 border-color: var(--border-tertiary);
 border-left-width: 2px;
 color: var(--text-secondary);
 font-size: .875rem;
 margin-bottom: 1rem;
 margin-top: 1rem;
 overflow: visible;
 padding-left: 1rem;
">
输入： energy = [-2,-3,-1], k = 2

输出： -1

解释：可以从魔法师 2 开始，吸收能量 -1。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= energy.length &lt;= 105</code></li>
	<li><code>-1000 &lt;= energy[i] &lt;= 1000</code></li>
	<li><code>1 &lt;= k &lt;= energy.length - 1</code></li>
</ul>

&nbsp;