53. 最大子数组和

53. 最大子数组和 - 力扣（LeetCode）

class Solution {
public:
  int maxSubArray(vector<int>& nums) {
    int pre = 0, maxAns = nums[0];
    for (const auto x: nums) {
      pre = max(pre + x, x);
      maxAns = max(maxAns, pre);
    }
    return maxAns;
  }
};

用 $f(i)$ 代表以第 $i$ 个数结尾的「连续子数组的最大和」，构造状态转移函数

$$ f(i)=\max\{f(i−1)+nums[i],nums[i]\} $$

此方程意为「如果前缀和加上当前指向的数，总体和会变大（也即前缀和是正数），那么就采取前者；否则，抛弃前缀和，重新开始计算」。

考虑结尾而非开头的原因，正是因为动态规划的特点是「保存已走过的路径」。动态规划不能预知未来，但是可以对先前所走过的路径进行保存，以供我们更好地进行利用。

二刷

class Solution {
public:
  int maxSubArray(vector<int>& nums) {
    int Max = INT_MIN;
    int Prefix = 0;
    for (int N : nums) {
      Prefix = std::max(Prefix + N, N);
      Max = std::max(Max, Prefix);
    }
    return Max;
  }
};

还是不能死记硬背，得理解这里的 Current 在经过 std::max() 赋值之后，它事实上就变成了 Current——换句话说，前缀和是工具而不是目的；同样地，设立一个 Max 也是工具，它完全只是为了追踪 Current 和历史当中的 Max 谁更大的。

这里对 Prefix 进行的取最大值操作其实暗含了如下逻辑：

if (Prefix < 0) Prefix = N;

也即「如果前缀和本身就是负的，那再怎么加也不可能比 N 大，所以直接把它 clamp 掉」。这样理解这个 std::max 在这里的作用。题解评论区里有句话挺好：

如果往事已成负担，那你需要扔掉过去重新开始

此外，题解列表当中的这一篇对于动态规划的「无后效性」的解释引得挺好的，试着理解一下，或许动态规划看上去就没有那么吓人了：

为了保证计算子问题能够按照顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」。

三刷

class Solution {
public:
  int maxSubArray(vector<int>& nums) {
    int LocalSum = 0;
    int GlobalSum = INT_MIN;
    for (int X : nums) {
      LocalSum = max(X, LocalSum + X);
      GlobalSum = max(LocalSum, GlobalSum);
    }
    return GlobalSum;
  }
};

我觉得这个LocalSum和GlobalSum的命名其实比什么Prefix之类的要稍微好理解点。