[leetcode]: 53. Maximum Subarray

Bertha 。 2022-06-15 02:37 166阅读 0赞

# 1.题目 #

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array \[-2,1,-3,4,-1,2,1,-5,4\],  
the contiguous subarray \[4,-1,2,1\] has the largest sum = 6.

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

求连续子数组的最大和。  
尝试用分治法解决它。

# 2.分析 #

用cur记录当前子数组的和  
用max记录历史最大值  
以\[-2,1,-3,4,-1,2,1,-5,4\]为例，遍历一遍看

> x=-2  
> cur=-2,max=-2  
> x=1  
> cur=1,max=1 (-2+1<1, cur=-2的贡献是反作用的,所以要舍弃-2)  
> x=-3  
> cur=-2,max=1 (cur=cur+x=1-3=-2)  
> x=4  
> cur=4,max=4 (-2+4<4, cur=-2的贡献是反作用的,所以要舍弃-2)  
> x=-1  
> cur=3,max=4 (cur=cur+x=4-1=3)  
> x=2  
> cur=5,max=5 (cur=cur+x=3+2=5)  
> x=1  
> cur=6,max=6 (cur=cur+x=5+1=6)  
> x=-5  
> cur=1,max=6 (cur=cur+x=6-5=1)  
> x=4  
> cur=5,max=6 (cur=cur+x=1+5)

因此，如果前面计算的连续子数组的和cur<0, 就舍弃。从当前位置重新开始。  
动态规划状态转移方程  
dp\[i\],i表示以位置i为结尾的连续子数组的和的最大值  
dp\[i\]=dp\[i-1\]+nums\[i\] dp\[i-1\]>0;  
dp\[i\]=nums\[i\], dp\[i-1\]<=0;

# 3.代码 #

class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            int max_cur = 0;
            int max_sofar = INT_MIN;
            for (int n : nums) {
                max_cur = max_cur > 0 ? max_cur + n : n;
                max_sofar = max_cur > max_sofar ? max_cur : max_sofar;
            }
            return max_sofar;
        }
        //动态规划
        int maxSubArray(vector<int>& nums) {
            int* dp = new int[nums.size()]();
            dp[0] = nums[0];
            for (int i = 1; i < nums.size(); i++) {
                dp[i] = dp[i - 1] > 0 ? dp[i - 1] + nums[i] : nums[i];
            }
            int maxP = INT_MIN;
            for (int i = 0; i < nums.size(); i++)
                maxP = dp[i] > maxP ? dp[i] : maxP;
            return maxP;
        }
    };