Sharing my very simple and clear C++ solution with O(n) time complexity

• ``````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;
}``````

• 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;
``````

}

• it does not need O(n) Space, just use" int temp "is ok.

• int maxSubArray(int A[], int n) {
if(n == 0){
return 0;
}
int temp;
temp = A[0];
int maxSum = A[0];
for(int i = 1; i < n; i++){
temp = max(temp + A[i], A[i]);
maxSum = max(maxSum, temp);
}
return maxSum;
}

• Good idea. Thanks for your comment

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.