"""
Given an integer array nums, find the 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.

"""


def max_subarray(nums: list[int]) -> int:
    if not nums:
        return 0

    accs = [0] * len(nums)
    accs[0] = nums[0]

    for i in range(1, len(nums)):
        accs[i] = max(accs[i - 1], 0) + nums[i]

    return max(accs)


if __name__ == "__main__":
    assert max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
    assert max_subarray([5, 4, -1, 7, 8]) == 23