学步园

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.

思路：

根据Wikipedia，这是Brown大学某教授给学生的一道练习题。之后被CMU某教授找到O(n)的解法。

这个解法的思路很简单。设两个变量，一个是如果以当前元素为最长子数组的最后一个元素，所能达到的最大值max_ending_here。另一个是已知的最大值max_so_far。

其实是一个动态规划问题。

max_subarray(A[n]) = max( max_subarray(A[n-1]), A[n], max_subarray(A[n-1)(+)A[n] );

也就是说，已知一个数组A[n]及其最大子数组max_subarray(A[n])，我们添加一个元素A[n+1]进去。则有三种可能的情况：

1. 添加进去元素的数组A[n+1]不影响A[n]的最大子数组。

2. 单独的A[n+1]

3. 以max_subarray(A[n])和A[n+1]以及两者之间的元素组合起来生成的数组。

其中，如果在增长过程中，现有的数组段的和是负数，马上就可以抛弃，因为在这种情况下，max_subarray要是包含这一段，值肯定会比不包括这一段要大。

题解：参考Wikipedia中给出的代码

class Solution {
public:
    int maxSubArray(int A[], int n) {
        if (n == 0)
            return 0;
        
        int max_ending_here = A[0];
        int max_so_far = A[0];
        for(int i = 1; i < n; ++i)
        {
            if (max_ending_here < 0)
                // So far we get negative values, this part has to be dropped
                max_ending_here = A[i];
            else
                // we can accept it, it could grow later
                max_ending_here += A[i];
                
            max_so_far = max(max_so_far, max_ending_here);
        }
        return max_so_far;
    }
};