Greedy Algorithms · Medium

Maximum Subarray (Kadane's Algorithm)

O(N) · O(1)

Step 1: Setup & Initialization - Kadanes Algorithm

Reset current sum whenever running sum drops below 0.

Array Elements & Pointers
10
[0]
20
[1]
30
[2]
40
[3]
50
[4]
Live Variables & Invariants
status:Initialized
pattern:Kadanes Algorithm
Step 1 / 3
33%
Solution Code
1
function maxSubArray(nums: number[]): number {
2
  let max = nums[0], curr = nums[0];
3
  for (let i = 1; i < nums.length; i++) {
4
    curr = Math.max(nums[i], curr + nums[i]);
5
    max = Math.max(max, curr);
6
  }
7
  return max;
8
}
LeetCode IDE Console

Test Cases

4 cases from Blind 75 & NeetCode 150

Ask for a hint whenever you get stuck.