This problem follows the Kadane's Algorithm pattern, commonly found in the Greedy category. Recognizing this pattern is key to solving it efficiently in an interview setting.
Track current sum. If it goes negative, reset to 0. Update max at each step.
If the running sum goes negative, any future subarray is better off starting fresh — that's why you reset to the current element.
maxSum = nums[0]
currentSum = 0
for num in nums:
currentSum = max(num, currentSum + num)
maxSum = max(maxSum, currentSum)
return maxSumPractice Maximum Subarray and similar Greedy problems with flashcards. Build pattern recognition through active recall.
Practice this problem