Problem Statement in English

You’re given an array nums. Your task is to find a subarray in it with the maximum sum.

Approach

There’s a bunch of ways in which you could go about doing this, with complexities like $O(2^n)$ , $O(n^2)$ and $O(n)$. The first 2 are trivial.

  • $O(2^n)$: This utilises backtracking, where you generate every single possible subarray and check its sum.
  • $O(n^2)$: This is powered by a nested loop, going over every possible subarray.
  • $O(n)$: This is the interesting one. We use a special algorithm - Kadane’s Algorithm.

Kadane’s Algorithm for finding the subarray with max sum is a relatively straightforward concept. It keeps track of the current and best sum so far.

The current sum is reset every time that it becomes negative. If you think about this logically, when adding something to an existing non-negative sum makes it negative, that sum can no longer be the maximum so far, so you can safely say that it won’t become the maximum sum in the future either. This makes for the foundation of the algorithm.

From there you just check to see if the current sum is the higher than the previously recorded best, and if it is, update the previous best to be this.

If all that didn’t make too much sense, it’s totally fine. Try going through the code and see if that patches any holes in your understanding of what makes this thing tick.

Solution in Python


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # init best sum to be the first element in `nums`
        bestSum = nums[0]
        # init current sum
        currentSum = 0

        for val in nums:
            # reset current sum if it's negative
            currentSum = max(currentSum, 0)
            # add the value at the current index to the current sum
            currentSum += val
            # update max sum accordingly
            bestSum = max(bestSum, currentSum)

        return bestSum

Complexity

  • Time: $O(n)$
    Since we iterate over $n$ elements at most.

  • Space: $O(1)$
    Since we only use a couple integer variables.

And we are done.