How much of this question is carefuly application of arithmetic laws? Computing the maximum subarray seems like a simpler form of the classic longest increasing subsequence, but with fewer edges in the graph and a more “monotonic” (?) recurrence.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        T = [nums[0]]
        for i in range(1, len(nums)):
            T.append(max(nums[i], nums[i]+T[i-1]))
        return max(T)

Recurrence

The recurrence, such that it is, is that T[i] is the maximum sum of the array nums[:i+1] (to use slice syntax) that must use i. As in other questions, we’re embedding a decision in our recurrence. That would explain how the final max(T) works.

The big question is how does the for loop maintain the recurrence? How do we know that T was computed correctly? I don’t have a formal write-up, but to me the intuition follows from:

1. If any prefix is >0, then it’s worth including that prefix.
2. If any prefix is <= 0, then it’s not worth including it.

Distinct from the classic problem of longest-increasing-subsequence, we are only allowed to make limited choices, here: we can either attach ourselves to an existing sub-array, or start a new sub-array. If the existing sub-array has a positive influence (turn of phrase), then we might as well jump aboard. The choices are “simple”, in that sense.

This is included with all the other dynamic programming questions listed here.