LeetCode53 Maximum Subarray Element

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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;
}
};
分享到 评论