Maximum Subarray DSA Solution - Kadane Algorithm - Study Chapter | QuizMaker

Maximum Subarray explained with brute force, Kadane optimization, dry run, edge cases, complexity, and Python, C++, Java code.

Read: 12m
Type: Chapter
Access: Free

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 1: Arrays

Learning Outcome

After this lesson, you should be able to explain why a negative running sum should be dropped and how Kadane's algorithm finds the best contiguous subarray.

Problem Statement

Given an integer array nums, return the largest possible sum of a non-empty contiguous subarray.

Input	Output	Why
`[-2, 1, -3, 4, -1, 2, 1, -5, 4]`	`6`	The subarray `[4, -1, 2, 1]` has sum `6`.

Brute Force Approach

Try every start index and extend to every end index while tracking the largest sum.

This is useful for understanding the problem, but it still checks too many ranges and costs O(n^2).

Optimized Approach

At each index, decide whether to extend the previous subarray or start fresh from the current number. If the previous running sum hurts the answer, drop it.

Keep two values: current, the best subarray sum ending at this index, and best, the best sum seen anywhere.

Exact Pseudocode

current = nums[0]
best = nums[0]
for i from 1 to length(nums) - 1:
  current = max(nums[i], current + nums[i])
  best = max(best, current)
return best

Reference Code

class Solution:
    def maxSubArray(self, nums):
        current = nums[0]
        best = nums[0]

        for value in nums[1:]:
            current = max(value, current + value)
            best = max(best, current)

        return best

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int current = nums[0];
        int best = nums[0];

        for (int i = 1; i < nums.size(); i++) {
            current = max(nums[i], current + nums[i]);
            best = max(best, current);
        }

        return best;
    }
};

class Solution {
    public int maxSubArray(int[] nums) {
        int current = nums[0];
        int best = nums[0];

        for (int i = 1; i < nums.length; i++) {
            current = Math.max(nums[i], current + nums[i]);
            best = Math.max(best, current);
        }

        return best;
    }
}

Sample Dry Run

value	current decision	current	best
-2	start	-2	-2
1	start at 1	1	1
-3	extend: 1 + -3	-2	1
4	start at 4	4	4
-1	extend	3	4
2	extend	5	5
1	extend	6	6

Complexity

Measure	Value	Reason
Time	O(n)	Each number is processed once.
Space	O(1)	Only running totals are stored.

Edge Cases

All numbers are negative. Return the largest single number.
Only one element.
Best subarray appears at the beginning or end.

Interview Checklist

Do not reset to zero if the problem requires a non-empty subarray.
Explain current as "best sum ending here".
Keep updating best after each current value.

FAQs

Why initialize with nums[0]?

The answer must be a non-empty subarray, so all-negative arrays should still return one element.

What is the key Kadane decision?

At every index, choose between starting fresh and extending the previous subarray.

Does this return the subarray itself?

This version returns only the sum. Track start and end indices if the platform asks for the actual subarray.