From: LeetCode53.
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
思路一
设置两个变量，一个记录当前连加的值，另一个记录目前位置最大连续子序列，迭代更新。本质上是贪心法的体现。
int MaxSubArray(const vector<int>& arr)
{
int max_so_far = INT_MIN;
int sum = 0;
for (int e : arr)
{
if (sum > 0)
sum += e;
else
sum = e;
max_so_far = max(max_so_far, sum);
}
return max_so_far;
}
// 等价写法一：从头开始累加，关键是什么时候丢弃当前的累加进度，重新开始。
// 答：当累加和小于当前元素的时候，不如丢弃累加和，直接从当前元素再开始累加。
int maxSubArray(vector<int>& nums) {
int ret = INT_MIN, sum = 0;
for (int e : nums)
{
sum = max(sum+e, e);
ret = max(ret, sum);
}
return ret;
}
// 等价写法二
int maxSubArray(vector<int>& nums) {
int sum = 0, ans = INT_MIN;
for (int e : nums) {
sum += e;
ans = max(ans, sum);
if (sum < 0) sum = 0;
}
return ans;
}思路二
上面的方法，其实算是贪心法。从前往后累加，遇到 sum < 0 就丢掉，重新开始累加，因为不丢掉肯定给最终的子数组的和带来负作用。其实这题还可以用动态规划的思想来做（EPI例题）。想要知道数组 A[n] 的最大子数组的和，如果知道 A[n-1] 的最大子数组的和会否有帮助呢？答案是不会。记 ，特别的，记 . 如果我们知道所有子数组 A[0:i], i ⇐ n-1 的最小和，那么用 和它作差就得到了 A[n-1] 的最大子数组和。同理 A[n] 也一样。
代码选自EPI，
int FindMaximumSubarray(const vector<int>& A) {
int min_sum = 0, sum = 0, max_sum = 0;
for (int i = 0; i < A.size(); ++i) {
sum += A[i];
if (sum < min_sum) {
min_sum = sum;
}
if (sum - min_sum > max_sum) {
max_sum = sum - min_sum;
}
}
return max_sum;
}这其实是前缀和贪心，经过前缀和的桥梁，转换成了枚举右维护左的典型题目。同时和 股票买卖问题I 建立联系。
// 前缀和贪心，子数组的和等于两个前缀和相减
// 维护左边出现的最小前缀和，每次用当前的前缀和减掉最小来更新答案（枚举右维护左，股票买卖I）
int maxSubArray(vector<int>& nums) {
int psum = 0, min_psum = 0;
int ans = nums[0];
for (int e : nums) {
psum += e;
ans = max(ans, psum - min_psum);
min_psum = min(min_psum, psum);
}
return ans;
}思路三
动态规划。
class Solution {
public:
// dp
int maxSubArray0(vector<int>& nums) {
const int n = nums.size();
vector<int> f(n + 1, 0); // f[i]: 以nums[i]结尾的最大子数组的和（实际上错位，填充f[0]方便处理边界）
int ans = nums[0];
for (int i = 0; i < n; ++i) {
f[i+1] = max(f[i], 0) + nums[i];
ans = max(ans, f[i+1]);
}
// 注意：f[n]并不是答案，因为他表示nums[n-1]必选，实际上未必选
// 答案应该是遍历过程中，以nums[i]结尾的“最大子数组和”的最大值。
return ans;
}
// dp + 空间优化：注意到算完f[i+1]后f[i]就用不到了
int maxSubArray(vector<int>& nums) {
int f0 = 0;
int ans = nums[0];
for (int e : nums) {
f0 = max(f0, 0) + e;
ans = max(ans, f0);
}
return ans;
}
};