leetcode-53. 最大子数组和

本文最后更新于：2022年7月30日 晚上

dp

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // 子数组是连续的部分
        // dp问题
        // dp[i]:表示数组nums[0,i]的最大连续子数组的和为dp[i]
        // dp[0] = nums[0]

        vector<int> dp(nums.size());

        dp[0] = nums[0];
        int res = dp[0];
        for (int i = 1; i < nums.size(); i++)
        {
            dp[i] = max(dp[i-1]+nums[i], nums[i]);
            if (dp[i] > res) res = dp[i];// 保存连续子数组最大和
        }

        return res;   
    }
};

贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // 贪心思路：遍历求和，如果和小于0，这和不要也罢，直接从下一个元素开始累加和

        int res = INT32_MIN;
        int sum = 0;
        // [-1]
        for (int i = 0; i < nums.size(); i++)
        {
            sum += nums[i];
            // 先使用sum更新res，否则先判断sum<0的话会把sum的值变为0，就丢失了原来的值了。
            if (sum > res) res = sum;// 先更新res
            if (sum < 0) sum = 0; // 再把小于0的sum变为0
        }

        return res;
    }
};