204. Maximum Subarray
Medium
Kadane's Algorithm
Array
Problem
Given an integer array nums, find the contiguous subarray with the largest sum and return its sum. The subarray must contain at least one element.
Examples
Example 1
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
The subarray [4,-1,2,1] has the largest sum 6.
Example 2
Input: nums = [1]
Output: 1
Example 3
Input: nums = [5,4,-1,7,8]
Output: 23
Constraints
� 1 <= nums.length <= 10⁵
� -10⁴ <= nums[i] <= 10⁴
Hints
?? At each position, decide whether to extend the previous subarray or start a new one.
?? Track the best sum ending at the current position.
?? Keep a global maximum while scanning the array.
Expected Complexity
Time: O(n)
Space: O(1)
Follow-up
Can you implement Kadane's Algorithm in O(n) time and O(1) space?
Practice Notes
Attempts: 0
Time spent: 0min
Hints used: 0
JavaScript
00:00
Loading...
Case 1
Case 2
Case 3
Input
[-2,1,-3,4,-1,2,1,-5,4]Expected
6