Description:
https://leetcode.com/problems/maximum-subarray/#/description
Algorithm:
Use dp, if dp[i – 1] < 0, discard.
if dp[i – 1] > 0, dp[i] = dp[i] + nums[i]
Code:
int maxSubArray(vector<int>& nums)
{
int maxSubArray(vector<int>& nums)
{
int n = nums.size();
vector<int> dp(n);
dp[0] = nums[0];
int res = nums[0];
for (int i = 1; i < n; i++)
{
if (dp[i - 1] < 0)
dp[i] = nums[i];
else
dp[i] = dp[i - 1] + nums[i];
res = max(res, dp[i]);
}
return res;
}
Timing:
9ms, fastest