O(N) Time complexity and O(1) Space Complexity


  • 0
    R

    Explanation: This question is a classic DP problem. We can solve the problem by updating the maximum value and temporary sum value while iterating through the array.

    The array can be viewed like this [n1,n2,n3...] @ [s1, s2, s3, ...] @ num.
    We have the temporary sum of the subarray [s1, s2, s3, ...], we call it "tmp_sum". When we read in a new number, there will be two cases:

    case 1: The new number should be reset as the start (head) of a new sub-array.

    case 2: The new number will be added to the former sub-array.

    The decision of this condition is simple that if the new number is larger than the sum of previous sub-array and itself, then we should set it as the start of a new sub-array. The reason is simple that if starting with the new number is better (larger) than making it as a member of the previous sub-array, why not start it as a new sub-array?

    if (num > num + sum([s1, s2, s3, ...]))
       set num as head of a new sub-array
    else
       tmp_sum = tmp_sum + num;
    

    If num > num + sum([s1, s2, s3, ...]), then sum([s1, s2, s3, ...]) < 0. However, we won't use 0 directly, because if all the values in the sum are negative, then the maximum can't be calculated correctly.

    And every time, we need to update the temporary max to memorize the maximum value till now. Temporary sum will not do that.

    Java:

    public int maxSubArray(int[] nums) {
        int tmp_max = Integer.MIN_VALUE;
        int tmp_sum = 0;
        
        for(int num : nums)
        {
            tmp_sum = Math.max(num, tmp_sum + num);
            tmp_max = Math.max(tmp_max, tmp_sum);
        }
        return tmp_max;
    }

  • 0
    F

    This is not a DP solution, nor is it O(log n)!


  • 0
    R

    Thank you for pointing out! I'm careless when writing about question names!


Log in to reply
 

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