<Data Structures/Algorithms> leetcode hot100 - 53. Maximum Subarray

[LeetCode Hot 100] 53. Maximum Subarray

Problem Link

For this problem, the approach is based on dynamic programming. We create an array maxSum where maxSum[i] represents the maximum subarray sum ending at index i.

The logic is:

• If the previous maximum subarray sum maxSum[i-1] is positive, it contributes positively to maxSum[i], so we add nums[i].
• Otherwise, it’s better to start a new subarray from nums[i].

Thus:

maxSum[i] = max(maxSum[i-1] + nums[i], nums[i])

Finally, take the maximum value among all maxSum[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;
    }
};

中文原文

[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;
    }
};