Maximum Subarray

     int maxSubArray(int A[], int n) {
        vector<int > dp(n,0);
        dp[0]=A[0];
        int amax=A[0];
        for(int i=1;i<n;i++){
            dp[i]=A[i]+(dp[i-1]>0?dp[i-1]:0);
            amax=max(dp[i],amax);
        }
        return amax;
    }
 //less space
    int maxSubArray(int A[], int n) {
        int mx,pre;
        mx=pre=A[0];
        for(int i=1;i<n;i++){
            if(pre>0)
                {pre+=A[i];}
            else
                pre=A[i];
            if(pre>mx) mx=pre;   
        }
        return mx;       
    }