Data Structures and Algorithms (DSA)  

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

  1. Start by assigning the first element of the array to both currentSum and maxSum

  2. Move through the array one element at a time

  3. 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]

ElementcurrentSummaxSum
-2-2-2
111
-3-21
444
-134
255
166
-516
456

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.

Membership not found