【题意】给一个数组，找出连续的和最大的子数组
【解】把数组分成左右两部分，最大的子列有三种可能：出现在左半部分，右半部分，横跨左右两部分。
前两种递归解，最后一种是从中间的位置向两边延伸，O(n)扫一遍记录和最大的。
时间复杂度T(n) = T(n/2)+O(n)，T(n) = O(nlogn)
class Solution { public: int maxSubArray(vector<int>& nums) { int result = 0; int n = nums.size(); pair<int, int> range = f(nums, 0, n); for (int i = range.first; i < range.second; i++) result += nums[i]; if (range.first == range.second){ int m = nums[0]; for (int i = 0; i < n; i++) if (nums[i] > m) m = nums[i]; return m; } return result; } private: pair<int, int> f(vector<int>& nums, int l, int r){ if (r - l == 1){ if (nums[l] >= 0) return make_pair(l, r); else return make_pair(r, r); } pair<int, int> lmax = f(nums, l, (l + r) / 2); pair<int, int> rmax = f(nums, (l + r) / 2, r); int sum1 = 0, index1 = (l + r) / 2 - 1, msum1 = nums[index1]; for (int i = (l + r) / 2 - 1; i >= lmax.first; i--){ sum1 += nums[i]; if (sum1 >= msum1){ msum1 = sum1; index1 = i; } } int sum2 = 0, index2 = (l + r) / 2, msum2 = nums[index2]; for (int i = (l + r) / 2; i < rmax.second; i++){ sum2 += nums[i]; if (sum2 >= msum2){ msum2 = sum2; index2 = i; } } int ll = 0; for (int i = lmax.first; i < lmax.second; i++) ll += nums[i]; int rr = 0; for (int i = rmax.first; i < rmax.second; i++) rr += nums[i]; if (ll >= rr && ll >= msum1 + msum2) return lmax; else if (rr >= ll && rr >= msum1 + msum2) return rmax; else return make_pair(index1, index2 + 1); } };============================================================分割线===================================================================【解法2】双指针，如果算出和小于零，就不选这部分
算法:
left = 0,right = 1
max = nums[0]
if (sum[left,right) < 0)
left = right
if (sum[left,right) > max)
max = sum([right, left))
right++
算和的时候可以用前一步的和推
时间复杂度O(n)，空间O(1)
class Solution { public: int maxSubArray(vector<int>& nums) { int left = 0, right = 1; int maxSum = nums[0]; int curSum = 0; int n = nums.size(); while (right <= n) { curSum += nums[right - 1]; if (curSum > maxSum) maxSum = curSum; if (curSum < 0) { left = right; curSum = 0; } right++; } return maxSum; } };【解法3】动态规划
dp[i]表示以nums[i]为结尾的最大子数列和。
dp[i] = max {dp[i - 1] + nums[i], nums[i] }，求得dp[0...n-1]之后找最大的即可。
时间复杂度O(n)，空间O(n)。空间可以优化到O(1)，因为只用了dp[i]和dp[i - 1]，和上面的方法有相似的地方。
class Solution { public: int maxSubArray(vector<int>& nums) { int n = nums.size(); if (!n) return 0; vector<int> dp(n); dp[0] = nums[0]; for (int i = 1; i < n; i++) { dp[i] = nums[i] > dp[i - 1] + nums[i] ? nums[i] : dp[i - 1] + nums[i]; } int max = 0; for (int i = 0; i < n; i++) { if (dp[i] > max || i == 0) max = dp[i]; } return max; } };