LeetCode53 Maximum Subarray Element


描述

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

样例

1
2
Input:
[-2,1,-3,4,-1,2,1,-5,4]
1
2
Output:
6

思路

求数组最大子串和。

定义$dp[i]$为以第$i$个元素结尾的最大子串和。

显然,当$dp[i-1] > 0$时,$ dp[i] = dp[i-1] + nums[i]$,否则$dp[i] = nums[i]$

最后$ans = max(dp[i] | i = 0..n-1)$

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum = 0, ans = INT_MIN;
for (int& x: nums) {
sum < 0 ? sum = x : sum += x;
ans = max(ans, sum);
}
return ans;
}
};