题目

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

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

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

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

示例 1：

输入： energy = [5,2,-10,-5,1], k = 3

输出： 3

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

示例 2：

输入： energy = [-2,-3,-1], k = 2

输出： -1

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

提示：

• 1 <= energy.length <= 10^5
• -1000 <= energy[i] <= 1000
• 1 <= k <= energy.length - 1

解题思路

解法一：从后向前（后缀和动态规划）

这种方法更像是一种“回顾型”的思路，它直接、清晰地构建出每个可能的起点对应的总能量。

• 核心逻辑: “从 i 点出发的总能量，等于 i 点自身的能量，加上从 i 的下一个点 i+k 出发的总能量。” 这个关系可以表示为：TotalEnergy(i) = energy[i] + TotalEnergy(i+k)。
• 执行过程:
  1. 从后向前遍历整个 energy 数组（例如，从 n-1 到 0）。
  2. 这样做的好处是，当我们计算 TotalEnergy(i) 时，TotalEnergy(i+k) 的值已经被计算并更新在 energy[i+k] 的位置上了。
  3. 我们直接在原数组上进行更新。循环结束后，energy[i] 的值就不再是它初始的能量，而是以 i 为起点能获得的总能量。
  4. 最后，遍历这个被完全更新过的 energy 数组，找到其中的最大值，即为答案。
• 特点:
  • 直观: 逻辑与问题的定义（从某点出发走到最后）高度吻合。
  • 空间效率高: 可以直接在输入数组上修改（原地操作），空间复杂度为 $O(1)$。
  • 信息完整: 最终数组保留了每一个可能的起点所对应的总能量。

解法二：从前向后（最大后缀和动态规划）

这种方法是一种“前进型”的思路，它在前进的过程中动态地维护每个组的最优解。

• 核心逻辑: 对于每个独立的路径，在向前走的过程中，时刻保持一个“当前最优路径和”。当遇到一个新元素 x 时，决策如下： “是将 x 添加到当前最优路径上，还是因为当前最优路径和已是负数（会拖后腿），干脆抛弃它，从 x 重新开始一段新的路径？” 这个关系可以表示为：NewBestSum = max(x, x + OldBestSum)。
• 执行过程:
  1. 创建一个大小为 k 的辅助数组 ans，用于分别追踪 k 条路径的“当前最优路径和”。
  2. 从前向后遍历整个 energy 数组（例如，从 0 到 n-1）。
  3. 根据当前索引 i，更新 ans[i % k] 的值。
  4. 循环结束后，ans[j] 中存储的就是第 j 条路径的最终最优解（即这条路径的“最大后缀和”）。
  5. 最后，遍历 ans 数组，找到其中的最大值，即为答案。
• 特点:
  • 巧妙: 算法逻辑非常精炼，是动态规划思想的经典应用。
  • 需要额外空间: 需要一个大小为 k 的辅助数组，空间复杂度为 $O(k)$。
  • 信息聚焦: 最终只保留了 k 个最优结果，而不是所有可能起点的结果。

具体代码

解法一

func maximumEnergy(energy []int, k int) int {
    n := len(energy)
    maxE := math.MinInt32

    // 从后向前遍历数组
    // 在这个单次循环中，我们既计算每个起点的总能量，又同时跟踪最大值
    for i := n - 1; i >= 0; i-- {
        // 步骤 1: 更新当前位置的总能量 (与之前的逻辑相同)
        if i+k < n {
            energy[i] += energy[i+k]
        }
        // 步骤 2: 将更新后的总能量与已知的最大值进行比较
        // 因为 energy[i] 在此时已经代表了从 i 出发的路径总能量，
        // 所以可以直接用来更新全局最大值。
        if energy[i] > maxE {
            maxE = energy[i]
        }
    }

    return maxE
}

解法二

func maximumEnergy(energy []int, k int) int {
	// 创建一个大小为 k 的数组，用于分别存储 k 条独立路径的当前计算结果。
	// ans[j] 对应所有索引 i 满足 i % k == j 的路径。
	ans := make([]int, k)
	
	// 初始化全局最大值为一个极小值。
	mx := math.MinInt

	// 从头到尾遍历能量数组。
	for i, x := range energy {
		// i % k 用于确定当前能量值 x 属于 k 条路径中的哪一条。
		
		// 这里的 if/else 是一种计算“最大后缀和”的巧妙方法。
		// 它等价于 ans[i%k] = max(x, ans[i%k] + x)。
		if ans[i%k] < 0 {
			// 如果某条路径当前的累加和变成了负数，
			// 那么它对后续的累加只会起到负面作用，不如直接丢弃，从当前元素 x 重新开始。
			ans[i%k] = x
		} else {
			// 如果累加和是非负的，则继续累加当前元素 x。
			ans[i%k] += x
		}
	}

	// 第一个循环结束后，ans 数组中存储了 k 条路径各自的最优解（即最大后缀和）。
	// 现在，只需遍历 ans 数组，找到这 k 个最优解中的最大值。
	for _, x := range ans {
		mx = max(mx, x)
	}
	
	// 返回全局最大能量值。
	return mx
}