Maximum Subarray（最大的连续子数组） 【面试算法leetcode】

题目：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.

题意 求连续的子串和最大。

贪心的做法，可以线性时间解决。如果之前的连续状态是正数，加上后面的值肯定能更大，如果是负数，就不要加了，now赋值成零。

class Solution {public:    int maxSubArray(int A[], int n) {        int now=0,maxx=-1<<29;        for(int i=0;i<n;++i)        {            now+=A[i];            maxx=max(now,maxx);            if(now<0)now=0;                    }        return maxx;            }};