LC 0053 [E] Maximum Subarray - ALawliet/algorithms GitHub Wiki
DP, S: O(n)
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
T = [0] * n
T[0] = nums[0]
res = nums[0]
for i in range(1, n):
# T[i] = nums[i] + (T[i-1] if T[i-1] > 0 else 0)
T[i] = max(T[i-1] + nums[i], nums[i]);
res = max(res, T[i])
return res
DP only uses 2 cells at a time so we can just optimize by using 2 variables
greedy / optimized DP, S: O(1)
class Solution:
def maxSubArray(self, nums):
cumsum = 0
res = float('-inf')
for x in nums:
cumsum = max(cumsum + x, x)
res = max(res, cumsum)
return res