53. Maximum Subarray

Recursive Program Specification:

terminate if i==n
max(nums[i], curr_res + nums[i])
max(max_res, curr_res)          else

For each element, we can the choice to include that element or reset the curr_res to startover and begin with that element. That's why we have to do max(nums[i], curr_res+nums[i]), we want to know that if it is worth it to restart the element or just keep that element and keep growing. And we can just keep the maximum of the curr result and the max result in each iteration

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        curr = nums[0]  # Initialize with the first element
        best = nums[0]  # Initialize with the first element
        
        for i in range(1, len(nums)):  # Start from the second element
            curr = max(nums[i], curr + nums[i])  # Choose max between adding or starting fresh
            best = max(curr, best)  # Update best if current is greater
            
        return best