Given an integer array nums, find the subarray 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.
1 <= nums.length <= 105-104 <= nums[i] <= 104
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# Initialize current_max to the first element and global_max to a very small number
current_max = global_max = nums[0]
# Iterate over the array starting from the second element
for num in nums[1:]:
# Update current_max either by adding the current num or starting a new subarray with num
current_max = max(num, current_max + num)
# Update global_max to be the maximum value found so far
global_max = max(global_max, current_max)
return global_maxRemove when coming across negetive prefix in sliding window.
O(n) - The algorithm iterates through the array exactly once, performing constant-time work for each element.
O(1) - Only a fixed number of variables are used, regardless of the input size.