ByteByteGo: Maximum Subarray Sum
β’ 65 words β’ 1 min β’ updated
ByteByteGo: Maximum Subarray Sum:
python
from typing import List
def maximum_subarray_sum(nums: List[int]) -> int:
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(i, must_take=False):
if i < 0:
return 0
if i == 0:
if must_take:
return max(0, nums[i])
else:
return nums[i]
take = nums[i] + solve(i - 1, True)
if must_take:
return max(0, take)
skip = solve(i - 1)
return max(take, skip)
return solve(len(nums) - 1)