Kadane's Algorithm | Maximum Subarray Sum | Finding and Printing

Main Ideas

• Goal: Find the largest possible sum among all contiguous subarrays of an array.
• A subarray contains consecutive elements. For example, [-1, -2] is a subarray, but choosing separated elements such as -1 and 5 is not. A subarray can contain one element or the entire array.
• For [-2, -3, 4, -1, -2, 1, 5, -3], the maximum-sum subarray is [4, -1, -2, 1, 5], with a sum of 7.

Approaches

1. Brute Force: Enumerate and Sum Every Subarray

• Choose each possible starting index i.
• For each i, choose every ending index j ≥ i.
• For every pair (i, j), loop from i to j to calculate the subarray’s sum.
• Keep track of the greatest sum found.

Time: O(n³) Extra space: O(1)

2. Improved Approach: Extend a Running Sum

• Choose each starting index i and initialize a running sum to zero.
• Extend the subarray one element at a time, adding each new element as the ending index advances.
• Update the maximum after each addition.

This avoids recalculating the sum of the entire subarray each time.

Time: O(n²) Extra space: O(1)

3. Optimal Approach: Kadane’s Algorithm

• Maintain a running sum and the best sum found so far.
• Add each array element to the running sum, then compare it with the best sum.
• If the running sum becomes negative, reset it to zero. Carrying a negative sum forward can only reduce the sum of a future subarray.
• Keep a positive running sum even if it includes negative elements; it may still contribute to a larger sum later.
• For the example array, the best sum reaches 7.

Time: O(n) Extra space: O(1)

Printing a Maximum-Sum Subarray

Track three indices:

• start: the beginning of the current subarray
• answerStart: the beginning of the best subarray found so far
• answerEnd: the end of the best subarray found so far

When the running sum is zero and a new subarray is about to begin, set start to the current index. Whenever the running sum exceeds the best sum, save start as answerStart and the current index as answerEnd.

These indices identify one maximum-sum subarray. If multiple subarrays tie, the method may return any one of them. This tracking does not change Kadane’s complexity: O(n) time and O(1) extra space.

Empty-Subarray Convention

The video discusses a version of the problem that permits an empty subarray, whose sum is zero. If every element is negative, the best non-empty subarray has a negative sum, but the permitted empty subarray makes the answer 0.

Use a sufficiently wide integer type, such as long long, for sums when needed.

Speakers and Sources

The presenter is an instructor from Take U Forward, teaching the Striver A to Z DSA course. No other actual speakers are featured; interviewers are mentioned only as hypothetical examples.