Leetcode: Max Subarrray

Maximum Subarray | LeetCode OJ

Let’s analyse the input first, we have an unsorted array of integers and we are not allowed to change the order. So our only option is traversing the array. Now we need to find a contiguous sequence satisfying some property. This can be done by checking sequences of all size starting at each point or alternatively ending at each point. Checking for sequences of all sizes would use O(n²) time complexity.

To optimize we need to avoid checking for all sequences and use the results of previous sequences to calculate the result for current sequence

1. Traverse the array from left to right and keep track of maximum sum at each element
2. To do that, check the maximum sum at previous element and add the current element to it if it makes the sum larger or just use the current element
3. Keep track of the maximum sum obtained at each element

Remarks:

1. O(1) space complexity as constant number of variables are being used
2. O(n) time complexity for traversing the array once
3. Using result of previous element to find result of current element, you will see this pattern in a lot of places

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return None
        res = nums[0]
        sum = res
        for n in nums[1:]:
            sum = n if sum < 0 else sum + n
            res = max(sum, res)
        return res