力扣算法篇：连续子数组的最大和

Dp

dp五部曲：

1、确定dp数组的含义
dp[n]:意为以第n位数为结尾的最大子数组的和
2、确定递推式
dp[n]取决于dp[n-1]的值
        //如果dp[n-1]＞=0，dp[n]=dp[n-1]+nums[n-1]
        //如果dp[n-1]＜0,dp[n] = nums[n-1]
3、初始化
dp[1] = nums[0];
4、确定dp的计算顺序 自底向上
5、举例推导dp
1
2
3
4
5
6
7
8
9
10

题解

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //动态规划 
        //dp[n]:意为以第n位数为结尾的最大子数组的和
        //递推式：取决于dp[n-1]的值
        //如果dp[n-1]＞=0，dp[n]=dp[n-1]+nums[n-1]
        //如果dp[n-1]＜0,dp[n] = nums[n-1]
        //初始化
        int n = nums.size();
        vector<int> dp(n+1,0);
        dp[1] = nums[0];
        //计算dp数组
        for(int i = 1;i<=n;i++){
            if(dp[i-1]>=0){
                dp[i] = dp[i-1]+nums[i-1];
            }else{
                dp[i] = nums[i-1];
            }
        }
        //dp数组的最大值即为所求
        int max = *max_element(dp.begin()+1,dp.end());
        return max;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

分治法

定义一个操作 get（a,l,r）表示查询a序列[l,r]区间内的最大子段和
对半分 m = (l+r)/2 对区间[l,m],[m+1,r]分治求解
对每个区间维护四个变量

class Solution {
public:
    struct Status{
        //[l,r]以l为左端点的最大子数组和
        int lSum;
        //[l,r]以r为右端点的最大子数组和
        int rSum;
        //[l,r]区间内的最大子数组和
        int mSum;
        //[l,r]的区间和 用于合并区间时处理维护的信息值
        int iSum;
    };
    int maxSubArray(vector<int>& nums) {
      return get(nums,0,nums.size()-1).mSum;

    }

    //合并左右子区间的信息变量
    Status handle(Status left,Status right){
        //计算lSum，rSum，mSum，iSum
        int iSum = left.iSum+right.iSum;
        int lSum = max(left.lSum,left.iSum+right.lSum);
        int rSum = max(right.rSum,left.rSum+right.iSum);
        int mSum = max(max(left.mSum,right.mSum),left.rSum+right.lSum);
        return (Status){lSum,rSum,mSum,iSum};
    }

    Status get(vector<int>& a,int l,int r){
        //判断区间是否达边界
        if(l == r){
            //边界条件了 所有维护变量均为a[l]
            return (Status){a[l],a[l],a[l],a[l]};
        }
        //否则
        int m = (l+r)/2;
        //递归调用求解
        Status left = get(a,l,m);
        Status right = get(a,m+1,r);
        //返回合并的变量值
        return handle(left,right);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42