int maxSubArray(int A[], int n) {
if(n == 0){
return 0;
}
int* dp = new int[n];
dp[0] = A[0];
int maxSum = A[0];
for(int i = 1; i < n; i++){
dp[i] = max(dp[i  1] + A[i], A[i]);
maxSum = max(maxSum, dp[i]);
}
return maxSum;
}
Sharing my very simple and clear C++ solution with O(n) time complexity

your Space is O(n)， your method is very good， it's used dynamic planning.
The following is mine.int maxSubArray(int A[], int n) { int ccursum = 0, maxsum = 0,max=A[0]; bool mark = false; //remark the data ,if there are all negative number ,then mark =false. for (int i = 0; i < n; i++) { max = max>A[i] ? max : A[i];// record the max data ， if (mark(A[i] >= 0)) mark = true; ccursum += A[i]; if (ccursum < 0) ccursum = 0; maxsum = maxsum > ccursum?maxsum:ccursum; } if (maxsum == 0 && mark == false) { maxsum = max; // all negative number ,then maxsum = max } return maxsum;
}