题目描述

在这里插入图片描述

题解一：贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        if(len == 0) return -2147483648;
        //当前和
        int cur_sum = nums[0];
        //最大和
        int max_sum = nums[0];
        for(int i = 1; i < len; ++i)
        {
            cur_sum = max(nums[i], cur_sum + nums[i]);
            max_sum = max(max_sum, cur_sum);
        }
        return max_sum;
    }
};

在这里插入图片描述

题解二：动态规划

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0, max_sum = nums[0];
        for (const auto &x: nums) {
            pre = max(pre + x, x);
            max_sum = max(max_sum, pre);
        }
        return max_sum;
    }
};

在这里插入图片描述