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.
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
法I：动态规划。使用一个变量存储到i之前的sum，如果<0则忽略，记作0。使用另一个变量存储目前为止出现过的最大sum。
class Solution { public: int maxSubArray(int A[], int n) { int maxSum = A[0]; int subarraySum = A[0]; for(int i = 1; i < n; i++) { subarraySum = subarraySum <= 0? A[i] : subarraySum+A[i]; if(subarraySum > maxSum) maxSum = subarraySum; } return maxSum; } };
法II：分治法
从头到尾遍历目标数组，将数组分割为除了最后一个子串之外，其余子串的各元素之和小于0，且对于每个字串，最大和存在于某一前缀。然后比较各子串的最大前缀和，得到最终答案。我们以array={−2, 1, −3, 4, −1, 2, 1, −5, 4}为例，来简单说明一下算法步骤。通过遍历，可以将数组分割为如下3个子串（-2），（1，-3），（4，-1，2，1，-5，4），这里对于（-2）这样的情况，单独分为一组。各子串的最大前缀和为-2，1，6，所以目标串的最大子串和为6。
int Kadane(const int array[], size_t length, unsigned int& left, unsigned int& right) { unsigned int i, cur_left, cur_right; int cur_max, max; cur_max = max = left = right = cur_left = cur_right = 0; for(i = 0; i < length; ++i) { cur_max += array[i]; if(cur_max > 0) { cur_right = i; if(max < cur_max) { max = cur_max; left = cur_left; right = cur_right; } } else { cur_max = 0; cur_left = cur_right = i + 1; } } return max; }
53. Maximum Subarray (Array; DP)
原文：http://www.cnblogs.com/qionglouyuyu/p/4857251.html