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.
Example 1:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
分析
当我们从头到尾遍历这个数组的时候，对于数组里的一个整数，它有几种选择呢？它只有两种选择： 1、加入之前的SubArray；2. 自己另起一个SubArray。那什么时候会出现这两种情况呢？
如果之前SubArray的总体和大于0的话，我们认为其对后续结果是有贡献的。这种情况下我们选择加入之前的SubArray
如果之前SubArray的总体和为0或者小于0的话，我们认为其对后续结果是没有贡献，甚至是有害的（小于0时）。这种情况下我们选择以这个数字开始，另起一个SubArray。
设状态为f[j]，表示以S[j]结尾的最大连续子序列和，则状态转移方程如下：
状态方程
解释如下：
- 情况一：S[j]不独立，与前面的某些数组成一个连续子序列，则最大连续子序列和为f[j-1]+S[j]。
- 情况二：S[j]独立划分成为一段，即连续子序列仅包含一个数S[j]，则最大连续子序列和为S[j]。
其他思路：
- 思路2：直接在i到j之间暴力枚举，复杂度是O(n^3)
- 思路3：处理后枚举，连续子序列的和等于两个前缀和之差，复杂度O(n^2)。
- 思路4：分治法，把序列分为两段，分别求最大连续子序列和，然后归并，复杂度O(nlog n)
- 思路5：把思路2O(n^2)的代码稍作处理，得到O(n)的算法
- 思路6：当成M=1的最大M子段和
思路：动态规划
class Solution {
public:
int maxSubArray(const vector<int>& nums) {
int maxLocal = nums[0];
int global = nums[0];
for (int i = 1; i < nums.size(); ++i) {
maxLocal = max(nums[i], nums[i] + maxLocal);
global = max(global, maxLocal);
}
return global;
}
};
时间复杂度o(n),空间复杂度o(1)
思路5
class Solution {
public:
int maxSubArray(vector<int>& A) {
return mcss(A.begin(), A.end());
}
private:
// 思路5，求最大连续子序列和
template <typename Iter>
static int mcss(Iter begin, Iter end) {
int result, cur_min;
const int n = distance(begin, end);
int *sum = new int[n + 1]; // 前n项和
sum[0] = 0;
result = INT_MIN;
cur_min = sum[0];
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + *(begin + i - 1);
}
for (int i = 1; i <= n; i++) {
result = max(result, sum[i] - cur_min);
cur_min = min(cur_min, sum[i]);
}
delete[] sum;
return result;
}
};
时间复杂度o(n),空间复杂度o(n)