Solution to LeetCode 53 Maximum Subarray & LeetCode 918 Maximum Sum Circular Subarray.
题目思想: “走完这一生， 如果我和你在一起会变得更好，那我们就在一起，否则我就丢下你。 回顾我最光辉的时刻就是和不同人在一起，变得更好的最长连续时刻。” – LeetCode Comments
LeetCode 53 | JZ 42
Maximum Subarray (Easy). [LeetCode link]
1] Greedy. Any time when the sum is negative (after adding nums[i]), restart from the next nums[i+1] and recalculate the sum from 0. Because negative number does not contribute to increasing the sum. Time complexity O(n), space complexity O(1).
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
res = -float('inf')
cnt = 0
for i in range(len(nums)):
cnt += nums[i]
if cnt > res: # find the max
res = cnt
if cnt <= 0: # restart if negative
cnt = 0
return res
2] Dynamic Programming. Define dp[i] as the max sum of the subsequence in the range of the [0,i] of the array. Suppose all numbers in nums are positive, when it comes to num[i], we add it to get larger sum, so we must have dp[i] = dp[i-1] + num[i]. However, any value in the num can be negative.
Case 1: dp[i-1] <= 0, including dp[i-1] won’t increase the sum, we have dp[i] = num[i].
Case 2: dp[i-1] > 0, including dp[i-1] will increase the sum, so we have dp[i] = dp[i-1] + num[i].
The function for DP is: max(nums[i], dp[i-1]+ nums[i]). If dp[i-1]+ nums[i] is smaller than nums[i], dp[i-1] has no contribution to the sum.
Time complexity O(n), space complexity O(n).
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dp= [0]*(len(nums))
dp[0] = nums[0]
for i in range(1, len(nums)):
dp[i] = max(dp[i-1] + nums[i], nums[i])
return max(dp)
Use a rolling array to reduce space complexity to O(1). Time complexity is still O(n).
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in range(1, len(nums)):
nums[i] += max(nums[i-1], 0)
return max(nums)
Reduced space using two variables:
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = nums[0]
cur = nums[0]
for i in nums[1:]:
cur = max(cur + n, n)
res = max(res, cur)
return res
LeetCode 918
Maximum Sum Circular Subarray (Medium). [link]
Case 1: max subarray is in the linear array. This case can be solved by applying the same method in LC53 max(dp).
Case 2: max subarray is on the circle, including the suffix and the prefix of the linear array. Consider re-arranging the suffix and prefix as “prefix + mid + suffix”. There is at least one element in ‘mid’ so that the subarray can be shorter than the whole array. This case can be solved by applying max(-mid), because we want max(prefix + suffix) = max(sum-mid) = sum + maxSubarray(-arr).
(Note one of the base case: when all elements are negative, the answer is the largest element.)
1] Recursive DP implementation
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
n = len(nums)
@cache
def dp(i,s):
if i == 0: return nums[i] * s
return nums[i]*s + max(0,dp(i-1,s))
max_p = max(dp(i,1) for i in range(n))
max_n = max(dp(i,-1) for i in range(n))
return max_p if max_p < 0 else max(max_p, sum(nums) + max_n)
2] Iterative implementation with space saved
class Solution(object):
def maxSubarraySumCircular(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
max_cur = nums[0]
max_res = nums[0]
min_cur = nums[0]
min_res = nums[0]
for i in nums[1:]:
max_cur = max(i, i + max_cur)
max_res = max(max_res, max_cur)
min_cur = min(i, i + min_cur)
min_res = min(min_res, min_cur)
if sum(nums) == min_res:
return max_res
return max(max_res, sum(nums) - min_res)
