Short and simple C++ - O(n) time, O(1) space


  • 0
    M

    Solution relies on knowing the highest possible sum when looking at the subarray to the right (iterating in reverse).

    int maxSubArray(int A[], int n) {
        int res = A[0], rightSum = 0;
        for(int i = n-1; i >= 0; --i){
            rightSum = max(A[i], A[i] + rightSum);
            res = max(res, rightSum);
        }
        
        return res;
    }

  • -1
    M

    If A is a list that all members are negative, then your solution is wrong


Log in to reply
 

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