LeetCode 53. Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.method
dp[i]：表示以i结尾的最大子数组和
如果加上nums[i]会让dp[i-1]变大的话，dp[i]=dp[i-1]+nums[i]，反之，如果不能变大，dp[i]就保持nums[i]本身就好
int maxSubArray(vector<int>& nums) {
vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
int res = dp[0];
for (int i = 1; i < nums.size(); i++) {
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
res = max(res, dp[i]);
}
return res;
}用2个变量就可以
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int dp0 = nums[0];
int dp1 = 0;
int res = dp0;
for (int i = 1; i < n; i++) {
dp1 = max(dp0 + nums[i], nums[i]);
res = max(res, dp1);
dp0 = dp1;
}
return res;
}如果改成dp[i]：表示区间[0, i]的最大子数组和
用上面的方法得到dp数组后，还需要对dp数组作更新，相当于找到最大的数，并将后边的元素都更新为这个最大数
然后就可以直接返回dp[n-1]，因为其就是表示[0, n-1]的最大子数组和
for (int i = 1; i < n; i++) {
dp[i] = max(dp[i], dp[i - 1]);
}
nums: -3 4 -2 3 -5 4 1
dp: -3 4 2 5 0 4 5
dp': -3 4 4 5 5 5 5两个不重叠子数组的最大和
给定一个数组，有正有负，乱序，要求找两个不重叠的子数组，使得这两个子数组元素的和最大。（一个子数组内元素下标是连续的。）
示例 1：
输入：[-3,1,2,3,-1,2,8,0,-1,-6,9,2]
输出：26先正向求0到i的最大子数组和，再逆向求n-1到i的最大子数组和，两者相加取最大值
int main(int argc, char const *argv[])
{
vector<int> nums = {-3,4,-2,3,-5,4,1};
int n = nums.size();
vector<int> left(n, 0);
vector<int> right(n, 0);
left[0] = nums[0];
right[n - 1] = nums[n - 1];
// 求[0,i]的最大子数组和
for (int i = 1; i < nums.size(); i++) {
left[i] = max(left[i - 1] + nums[i], nums[i]);
}
for (int i = 1; i < n; i++) {
left[i] = max(left[i], left[i - 1]);
}
// 求[i,n-1]的最大子数组和
for (int i = n - 2; i >= 0; i--) {
right[i] = max(right[i + 1] + nums[i], nums[i]);
}
for (int i = n - 2; i >= 0; i--) {
right[i] = max(right[i], right[i + 1]);
}
int res = 0;
for (int i = 0; i < n - 1; i++) {
res = max(res, left[i] + right[i + 1]); // [0,i] + [i+1,n-1]
}
cout << res << endl;
return 0;
}
10 [4, -2, 3] + [4, 1]
