Classic Problem: Finding the largest subarray
Explain: https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
Leetcode
=> PATTERN: Remember this code
def max_subarray(A):
max_current = max_global = nums[0]
for num in nums[1:]:
max_current = max(num, max_current + num)
max_global = max(max_global, max_current)
return max_global
Enhancement: Now we have maximum subarray. Now Calculate maximum subsequence from this subarray.
For example: The subarray [2, -1, 2, 3, 4] is the subarray with the maximum sum, and [2, 2, 3, 4] is the subsequence with the maximum sum.
=> PATTERN: Remember this code
def max_subarray(A):
max_current = max_global = max_subsequence = nums[0]
for num in nums[1:]:
max_current = max(num, max_current + num)
max_global = max(max_global, max_current)
max_subsequence = max(max_subsequence, max_subsequence + num, num)
return max_global, max_subsequence
ADVANCE: Find that subarray
=> Remember this code
def max_subarray(nums):
max_sum = nums[0]
start = end = 0
current_sum = nums[0]
current_start = 0
for i in range(1, len(nums)):
if nums[i] > current_sum + nums[i]:
current_sum = nums[i]
current_start = i
else:
current_sum += nums[i]
if current_sum > max_sum:
max_sum = current_sum
start = current_start
end = i
return nums[start:end+1]
