面试题之最大子数组和

https://leetcode.cn/problems/maximum-subarray

方法1：

由于任意一个连续子数组都可以用两个累计和相减算出来，所以可以在算累计和的过程中，维护一个之前已经算出来的累计和的最小值，当前累积和减去前面的最小累积和，就是可能的要求的值。另外累计和本身也是一个连续子数组。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int minSum = nums[0];
        int accuSum = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            accuSum += nums[i];
            res = std::max(res, std::max(accuSum - minSum, accuSum));
            minSum = std::min(minSum, accuSum);
        }
        return res;
    }
};

方法2：

纯粹的动态规划，依次计算以索引i结束的子数组的和的最大值s[i]，则有递推公式：

s[i+1] = max(s[i+1], s[i] + nums[i+1])

nums为输入数组。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int preSum = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            preSum = std::max(preSum + nums[i], nums[i]);
            res = std::max(res, preSum);
        }
        return res;
    }
};

问题扩展：见之前写的hackerrank上的Maximum Subarray Sum题解笔记，该问题更难一点，就是算和的时候是算的取模的结果，但基本思路还是跟上面的方法一类似，就是依次算累积和，然后想办法把前面的最小值给找出来。