题目

链接。

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

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

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

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

题解

思路比较简单，需要注意几个点。

1. 至少要选一个

2. 由于至少要选一个，初始值要设置足够小（include <climits>，设置为 INT_MIN）

3. 注意边界，只有一个元素（题目限制不为空元素）

class Solution {
public:
    int maximumEnergy(vector<int>& energy, int k) {
      int result = INT_MIN;
      // 遍历元素
      for (int i = 0; i < energy.size(); ++i) {
        // 第 k 个元素后才开始考虑累加
        if (i >= k) {
          energy[i] += energy[i-k];
        }
        // 由于必须至少选一个, 所以最后 k 个元素强制计算结果
        if (i >= energy.size() - k) {
          result = max(result, energy[i]);
        } else {
          // 在最后 k 个元素之前，如果累加和小于 0 则置 0 （不要选择）
          if (energy[i] < 0) energy[i] = 0;
        }
      }
      return result;
    }
};

int main() {
  Solution s;
  std::vector<int> v = {1};
  std::cout << s.maximumEnergy(v, 1) << std::endl;
  v = {-2,-3,-1};
  std::cout << s.maximumEnergy(v, 2) << std::endl;
  v = {5,2,-10,-5,1};
  std::cout << s.maximumEnergy(v, 3) << std::endl;
  return 0;
}