LeetCode53. 最大子数组和

LeetCode53. 最大子数组和

解题思路dp

代码

/*
数组长度n = 9,连续的区间
那区间长度为1的区间数量是，9个
区间长度为2的区间数量是8个
区间长度为3的连续的区间数量为7个
....
区间长度为9的区间数量为1个
*/
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT_MIN;

        for(int i = 0, last = 0; i < nums.size(); i++){
            last = nums[i] + max(0,last);
            result = max(last,result);
        }

        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21