Given an integer array nums, find the contiguous subarray (with at least one element) that has the largest sum, and return that sum.
Example 1
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
The subarray
[4,-1,2,1] adds up to 6.Example 2
Input: nums = [5,4,-1,7,8]
Output: 23
Taking the whole array is best.
Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
Hints
Frequently asked at: Amazon, Microsoft, Google, Adobe, Flipkart, TCS, Infosys
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force tries every start and end, O(n^2) even with running sums. The key insight (Kadane's algorithm): if the best sum ending at the previous index is negative, it can only hurt, so we drop it and start fresh at the current element. Otherwise we extend it. Tracking the best value seen across all positions gives the answer in one pass.
Algorithm
- Set
cur = nums[0]andbest = nums[0]. - For each next element
x, setcur = max(x, cur + x). - Update
best = max(best, cur). - Return
best.
Time:
O(n)Space: O(1)Interview tip: Do not start
best at 0: if every number is negative, the answer is the largest single element, not 0. Follow-up: return the start and end indices too.class Solution: def maxSubArray(self, nums: List[int]) -> int: cur = best = nums[0] # cur = best sum ending here for x in nums[1:]: cur = max(x, cur + x) # extend or restart best = max(best, cur) return bestCtrl + Enter runs the examples