Kadane's Algorithm is a dynamic programming approach to solve the maximum subarray problem efficiently. It iterates through the array, keeping track of the current maximum sum and the overall maximum sum encountered so far. This approach avoids unnecessary recalculations by discarding negative subarray sums.

This algorithm leverages the principle of optimality, meaning that the optimal solution to a problem can be constructed from optimal solutions to its subproblems. In this context, the subproblems are finding the maximum subarray ending at each position in the array.

Intuition:

Imagine you're walking through a number line. You want to find the path with the highest total. If your current path sum becomes negative, it's like walking backward – it's better to start a new path from the current location than to continue with a negative sum. This is the core idea behind Kadane's Algorithm.

The algorithm hinges on the idea that a negative subarray sum will always decrease the sum of any subsequent subarray. Therefore, if the current subarray sum becomes negative, we reset it to 0, effectively starting a new subarray from the next element.

Step-by-step thinking:

Initialize maxSub with the first element of the array. This ensures that if the array contains only negative numbers, the largest negative number will be returned.
Initialize curSum to 0. This variable will store the sum of the current subarray.
Iterate through the array:
- If curSum is negative, reset it to 0. This is because a negative curSum will always decrease the sum of any subsequent subarray.
- Add the current element n to curSum.
- Update maxSub with the maximum of maxSub and curSum. This ensures that maxSub always stores the largest subarray sum encountered so far.
Return maxSub.

Time Complexity: O(n)
Space Complexity: O(1)

Learn Complexity

72. Maximum Subarray

Understand Before Coding

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Example 3:

Constraints:

Learn

Topics

Companies

Hint

Use Cases