53. Maximum Subarray.md

53. Maximum Subarray

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

• Let arr[i..j] be a subarray starting at index i and ending with index j.
• Consider the set S(n) of all subarrays ending at index n. i.e. S(n) = {arr[i..n] | i <- [0..n]}.
• Let P(n) be the max sum of all subarrays in S(n)
• This problem asks to find the max P(n) where n <- [0..L-1].

Think by Dynamic Programming. We want to establish a recurrence relation between P(n) and P(n - 1).

For any arr[i..n] where i != n, it can be divided into 2 parts: arr[i..n-1] and arr[n]. Thus we have

S(n) = {arr[i..n - 1] + arr[n] | i <- [0..n-1]}
     & {arr[n]}

Notice that S(n-1) = {arr[i..n - 1] | i <- [0..n-1]}. We have the relation:

P(n) = max(P(n-1) + arr[n], arr[n])

Given above, we can come up with a solution like below.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        P = nums[:]
        for n in range(1, len(nums)):
            P[n] = max(P[n - 1] + nums[n], nums[n])
        return max(DP)

Optimization

Since we only need know P(n-1) to compute P(n), we need not maintain all previous values of P(n) in an array.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ret = p = nums[0]
        for n in range(1, len(nums)):
            p = max(p + nums[n], nums[n])
            ret = max(ret, p)
        return ret