Very simple C++ solution O(n)


  • 4
    H

    class Solution {
    public:

    int maxSubArray (int A[], int n) {
        
        int max_sum=-INT_MAX, sum=0;
    
        for (int i=0; i<n; ++i){
            sum+=A[i];
            sum=max(sum,A[i]);
    
            if (sum>max_sum)
                max_sum=sum;
        }
        return max_sum;
    }
    

    };


  • 0
    M

    Would you explain this solution? Thanks a lot.


  • 0
    O

    This is DP. For each step iterating in the input array, current maximum is the max b/w current iterator value and previous plus current iterator value.
    Be more traditional, we can create a new array same size as input array. Each index of the new array stores the maximum sum we can get at index. The entry case is new_array[0] = input_array[0].


Log in to reply
 

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