<数据结构/算法> leetcode hot100系列. 53.最大子数组和

[LeetCode hot 100] 53. 最大子数组和

题目链接

这种题我是实在不知道该怎么想出来了，不说思路了，直接说算法流程。

建立一个新的数组maxSum，这个数组下标为i的位置maxSum代表：nums数组中，以第i个数为结尾的子数组之和的最大值。这时就可以利用类似于前缀和的思路。假如我们已经得到了以第i-1个数为结尾的子数组之和的最大值即maxSum[i-1]，那么以第i位为结尾的子数组之和最大值maxSum[i]一定能够推出来。maxSum[i]的唯一也是最大的要求就是必须包含nums[i]，那么是否包含前面的其他数，其实maxSum[i-1]已经提前算过了。假如maxSum[i-1]大于0，就说明前面选出来的子数组是有正向增益的，要加上才能更大，因此maxSum[i] = maxSum[i-1] + nums[i]。否则就说明以nums[i-1]结尾的子数组里面，和最大也没有大于0的，那干嘛还要再带着这些累赘呢，因此这种情况下maxSum[i] = nums[i]

完整代码如下

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> maxSum(nums.size());
        int ans = INT_MIN;
        for(int i = 0; i < nums.size(); i++){
            if(i == 0) maxSum[i] = nums[i];
            else maxSum[i] = max(maxSum[i - 1] + nums[i], nums[i]);
            
            ans = max(ans, maxSum[i]);
        }
        return ans;
    }
};