leetcode-53-线性DP-最大子序和

发表于 | 分类于

题目

1.png

解法

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
// 动态规划
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        if(n == 1) return nums[0];
		
        // dp[i] = x 表示以第i个元素结尾的子序列的最大子序和
        vector<int> dp(n);
        dp[0] = nums[0];
        for(int i = 1; i < n; ++i){
            dp[i] = max(dp[i-1] + nums[i], nums[i]);
        }

        return *max_element(dp.begin(), dp.end());
    }
};

// 动态规划优化空间复杂度
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        if(n == 1) return nums[0];
        
        int tempSum = nums[0]; // 第i个元素结尾时的临时子序列的和
        int res = tempSum;     // 最终结果
        for(int i = 1; i < n; ++i){
            tempSum = max(tempSum + nums[i], nums[i]);
            res = max(res, tempSum);
        }

        return res;
    }
};