Maximum Subarray Sum Using Kadane’s Algorithm (DSA Explained with Example)

Introduction

The Maximum Subarray Sum problem is one of the most popular and frequently asked questions in Data Structures and Algorithms (DSA) interviews. This problem mainly checks how well you understand arrays and how efficiently you can optimize a solution.

In simple terms, the problem asks you to find a continuous part of the array whose elements add up to the largest possible sum.

This article explains everything in easy language, making it ideal for students, beginners, and job seekers.

What is the Maximum Subarray Sum Problem?

You are given an array of integers that can contain positive numbers, negative numbers, or both. Your task is to find a contiguous subarray (elements must be next to each other) that gives the maximum sum.

Example

Input:  [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6

Explanation

In the above array, the subarray [4, -1, 2, 1] produces the highest sum:

4 + (-1) + 2 + 1 = 6

Why Brute Force is Not a Good Approach

In the brute-force method, we calculate the sum of all possible subarrays and then find the maximum.

Problems with Brute Force

Too many subarrays to check
Takes a lot of time for large arrays
Time Complexity becomes O(n²)

Because of this inefficiency, brute force is not suitable for interviews or real-world applications.

What is Kadane’s Algorithm?

Kadane’s Algorithm is an optimized solution that solves the Maximum Subarray Sum problem in linear time.

The core idea is very simple:

If the current sum becomes negative, it is better to start fresh from the next element
Always keep track of the maximum sum found so far

This approach avoids unnecessary calculations.

How Kadane’s Algorithm Works (Step-by-Step)

We use two variables:

currentSum – stores the sum of the current subarray
maxSum – stores the maximum sum found till now

Steps Explained

Start by assigning the first element of the array to both currentSum and maxSum
Move through the array one element at a time
At each element:
- Decide whether to add it to the existing subarray or start a new one
- Update maxSum if currentSum becomes larger

Dry Run Example (Very Important)

Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Element	currentSum	maxSum
-2	-2	-2
1	1	1
-3	-2	1
4	4	4
-1	3	4
2	5	5
1	6	6
-5	1	6
4	5	6

Final Maximum Subarray Sum = 6

Kadane’s Algorithm Code Implementation

C++ Code

int maxSubArray(vector<int>& nums) {
    int currentSum = nums[0];
    int maxSum = nums[0];

    for (int i = 1; i < nums.size(); i++) {
        currentSum = max(nums[i], currentSum + nums[i]);
        maxSum = max(maxSum, currentSum);
    }
    return maxSum;
}

Java Code

public int maxSubArray(int[] nums) {
    int currentSum = nums[0];
    int maxSum = nums[0];

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

Python Code

def maxSubArray(nums):
    current_sum = nums[0]
    max_sum = nums[0]

    for i in range(1, len(nums)):
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)

    return max_sum

Time and Space Complexity

Time Complexity: O(n) because we traverse the array only once
Space Complexity: O(1) as no extra space is used

This makes Kadane’s Algorithm highly efficient.

Why This Problem is Important for Interviews

Frequently asked in technical interviews
Helps understand optimization techniques
Builds foundation for dynamic programming concepts
Commonly seen in companies like TCS, Infosys, Amazon, and Google

Summary

The Maximum Subarray Sum problem using Kadane’s Algorithm is a must-learn topic in DSA. It teaches how to convert an inefficient brute-force solution into an optimized linear-time approach. By understanding how and when to reset the running sum, you can efficiently solve large input problems. Mastering this algorithm will greatly help you in coding interviews and in solving many real-world array problems.