53. Maximum Subarray

53. Maximum Subarray

同121题.
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.

人家媳妇：
(O(n)) time, (O(1)) space.
想法：子序列若小于０，还不如重新设定子序列，既，通过 max(f+A[i],A[i]) 就可以搞定.

int maxSubArray(vector<int>& A) {
    int n = A.size();
    if (n == 0) return 0;

    int re = A[0], sum = 0, i;
    for (i = 0; i < n; i++) {
        sum += A[i];
        re = sum > re ? sum : re; //re 始终存着最大子序列的和
        sum = sum > 0 ? sum : 0; //重新设定子序列
    }
    return re;
}

这帮变态还应用了动态规划方法((DP approach)).