Maximum Subarray： https://leetcode.com/problems/maximum-subarray/
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [?2,1,?3,4,?1,2,1,?5,4]，
the contiguous subarray [4,?1,2,1] has the largest sum = 6.
More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
contiguous 连续的
解析：
1. 动态规划法
当从头遍历数组元素时，对于数组中的一个整数有几种选择呢？
两种：加入之前的subArray；自己另起一个新的subArray.那么时候会出现这两种状况：
- 当之前subArray 的总和大于 0 时，我们认为 其对后续结果是有贡献的，这种情况下，我们选择加入之前的subArray
- 当之前subArray 的总和小于等于0时，我们认为其对后续结果是没有贡献的，这种情况下，我们选择以当前数字开始，另起一个subArray
设状态f(j) 表示 以 nums[j] 为结尾的最大连续子序列的和，则状态转移方程如下：
f(j) = max{f(j)+nums[j], nums[j]},其中1<=j<=n
target = max{f(j)}, 其中1<=j<=n
class Solution {
public:// 时间复杂度 O(n)int maxSubArray(vector<int>& nums) {int result = INT_MIN;int sum = 0;for (int i = 0; i < nums.size(); i++) {sum = max(sum+nums[i], nums[i]);result = max(result, sum);}return result;}
};2. 分治法
最大连续子序列可能存在的三个区间：
1. 完全在nums[left, mid-1]
2. 完全在nums[mid+1, right]
3. 包含 nums[mid],然后向左右扩展
最后比较左子序列、右子序列和中间序列，得到最大和。
class Solution {
public:// 时间复杂度O(nlogn)int maxSubArray(vector<int>& nums) {return divide(nums, 0, nums.size()-1);}
private:int divide(vector<int>& nums, int left, int right) {if (left == right)return nums[left];if (left+1 == right)return max(nums[left]+nums[right], max(nums[left], nums[right]));int mid = (left+right)/2;int left_max = divide(nums, left, mid-1);int right_max = divide(nums, mid+1, right);// 求中间连续子序列的最大和int mid_max = nums[mid]; // 向左扩展int temp = mid_max;for (int i = mid-1; i >= left; i--) {temp += nums[i];mid_max = max(temp, mid_max);}// 向右扩展temp = mid_max;for (int j = mid+1; j <= right; j++) {temp += nums[j];mid_max = max(temp, mid_max);}return max(mid_max, max(left_max, right_max));}
};参考：
https://github.com/soulmachine/leetcode
http://blog.csdn.net/xshengh/article/details/12708291