53. Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum

Example 1:

• Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
• Output: 6
• Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

• Input: nums = [1]
• Output: 1
• Explanation: The subarray [1] has the largest sum 1.

Example 3:

• Input: nums = [5,4,-1,7,8]
• Output: 23
• Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

Solution

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        best, total = nums[0], nums[0]

        for i in range(1, len(nums)):
            if total < 0:
                total = nums[i]
            else:
                total = total + nums[i]
            best = max(best, total)

        return best