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


  • 0
    Z
    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;
    }

  • 0
    J

    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;
    

    }


  • 0
    H

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


  • 0
    H

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


  • 0
    Z

    Good idea. Thanks for your comment


Log in to reply
 

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