LeetCode 53. Maximum Subarray

Questions: https://leetcode.com/problems/maximum-subarray/

This is probably a very well-known problem with a well-known solution bearing some statistician's name. The problem asked one to find the contiguous subarray that yields the maximum sum. After a while, one should realize many of the problems that ask for a optimal subset or subarray probably involves some dynamic programming. So it is all about how one goes about formulating the problem into a dynamic programming problem.

Suppose we have found the maximum contiguous subarray that ends at all indices up to n=len(nuns). The global solution is simply the maximum among these. Afterall, the global maximum has to end at some index. No the question is: given the maximum contiguous subarray at index i, how does it help with finding the solution that ended at i+1? Since by definition, we have to include i+1 element in the contiguous subarray. We only have two choices, either we only keep the element at i+1, or we extend the previous maximum continuous subarray by append the element at i+1. We will pick the larger of the two to yield a solution to that array.

\begin{equation*} F(i+1) = \text{maximize} (nums[i+1], F(i) + nums[i+1]) \end{equation*}

When the problem is framed in this way, the solution is just rather obvious. I think most people with some practice will find Dynamic Programming solutions are not not as mysterious as they first seem to be, at least for the easier questions. This algorithm is named Kadane's algorithm, those who are interested can look it up on Wikipedia.

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)

        if n >= 1:
            a = nums[0]
            curMax = a
            for i in range(1, n):
                b = max(a + nums[i], nums[i])
                if b > curMax:
                    curMax = b
                a = b
        return curMax   

References:

• Rod Cutting Problem: https://monkeyinvestment.blogspot.com/2014/09/clrs-exercise-151-3-rod-cutting-problem.html
• Coin Change: https://monkeyinvestment.blogspot.com/2020/04/leetcode-322-coin-change.html