最大连续子列
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;
}思路二
上面的方法，其实算是贪心法。从前往后累加，遇到 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;
}类似的，动态规划模板思路。代码来自姚老师，
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] fMax = new int[n+1]; // 每一个元素都是以当前元素为结尾的子数组，这个子数组对应的和
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
fMax[i+1] = Math.max(fMax[i], 0) + nums[i]; //得到以x结尾的最大子数组和
res = Math.max(res, fMax[i+1]);
}
return res;
}