Kadane’s Algorithm (Maximum Subarray Sum) in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include<stdio.h>

int main() {
    int n, a[100], max=-1e9, sum=0;
    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        scanf("%d", &a[i]);
        sum += a[i];
        if(sum > max) max = sum;
        if(sum < 0) sum = 0;
    }
    printf("%d", max);
}

C Output

Input:  
8  
-2 -3 4 -1 -2 1 5 -3  

Output:  
7

C++ Program

#include<iostream>
using namespace std;

int main() {
    int n, a[100], max=-1e9, sum=0;
    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> a[i];
        sum += a[i];
        max = max > sum ? max : sum;
        if(sum < 0) sum = 0;
    }
    cout << max;
}

C++ Output

Input:  
5  
-1 2 3 -5 4  

Output:  
5

JAVA Program

import java.util.*;

class K {
    public static void main(String[] a) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), sum=0, max=Integer.MIN_VALUE;
        for(int i=0; i<n; i++) {
            int x = sc.nextInt();
            sum += x;
            max = Math.max(max, sum);
            if(sum < 0) sum = 0;
        }
        System.out.print(max);
    }
}

JAVA Output

Input:  
6  
-2 -1 6 -2 -3 4  

Output:  
6

Python Program

a = list(map(int, input().split()))
s = m = a[0]
for i in a[1:]:
    s = max(i, s+i)
    m = max(m, s)
print(m)

Python Output

Input:  
-2 1 -3 4 -1 2 1 -5 4  

Output:  
6

In-Depth Learning – Whole Concept in Paragraphs

What is Kadane's Algorithm?

Kadane's Algorithm is a well-known algorithm to find the Maximum Subarray Sum Problem solution. For an array of numbers (both positive and negative), the objective is to determine the maximum sum of any subarray (i.e., elements not skipped). It's a dynamic programming solution that takes linear time (O(n)), which is far faster than brute-force O(n²) solutions.

How the Code Works

The algorithm has two variables:

sum (current sum ending at current position)

max (maximum sum found so far)

Step-by-step:

Set sum and max to first element or to zero (implementation-specific).

Loop through the array:

Add current number to sum.

If sum is greater than max, update max.

If sum goes negative, set it to zero — because a negative prefix will make any future sum smaller.

This makes sure that we always think about the best possible subarray at any given point.

Example

Input:

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

Subarrays to consider:

4 → 4

4, -1 → 3

4, -1, -2 → 1

4, -1, -2, 1 → 2

4, -1, -2, 1, 5 → 7 ✅

4, -1, -2, 1, 5, -3 → 4

Answer: 7 is the maximum subarray sum → 4 + (-1) + (-2) + 1 + 5

Real-Life Analogy

Imagine Kadane's Algorithm as following your daily profit. Certain days you lose (negative numbers), certain days you make (positive numbers). You are interested in the most profitable sequence of consecutive days. If losing money exceeds your profit, you reset your sequence — similar to resetting the total when it dips below zero.

Where and When Is It Used?

Kadane's Algorithm is used extensively in:

Stock market analysis (maximum profit over a period of time)

Gaming score tracking

Data streaming (highest segment)

Dynamic programming practice

Interview questions (extremely popular at Amazon, Google, etc.)

This algorithm also serves as a basis for extensions such as:

2D Kadane's Algorithm (maximum submatrix sum)

Circular subarray sum

Maximum average subarray

Time and Space Complexity

Metric\tValue

Time\tO(n)

Space\tO(1)

It only goes through each element once and maintains sums in two variables — great for high-performance scenarios.

Pythonic Insight

In Python:

python

s = max(i, s+i)

This line chooses: is it optimal to restart at this element (i) or keep the current streak (s+i). The outer max maintains the best overall.

This is quick and clean.

SEO-Optimized Natural Paragraph for Ranking

Want to use Kadane's Algorithm to compute the maximum subarray sum in C, C++, Java, or Python? This tutorial teaches the most elegant and concise solution to one of the most renowned dynamic programming problems. Kadane's Algorithm effectively determines the greatest sum of consecutive elements in an array in O(n) time complexity. It's a popular interview question and must-know information for students, programmers, and competitive programming enthusiasts. Master the step-by-step reasoning, practical examples, and optimized code to feel confident about solving subarray sum problems in various languages.