← Back to DSA Course | Chapter 2: Arrays | Lesson 7 of 8

Kadanes Algorithm

In this page:

  1. Kadane's Idea
  2. Running Sum
  3. Maximum Subarray Details
  4. Circular Array
  5. Kadane's Practice

Kadane's Idea

Kadane's algorithm finds the maximum possible sum of any contiguous subarray in a single linear O(n) pass, which is dramatically faster than the O(n²) or O(n³) approaches that check every possible subarray directly.

Example: Kadane's Idea

#include <iostream>
using namespace std;
int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int maxSum = arr[0], curSum = arr[0];
    for (int i = 1; i < 9; i++) {
        curSum = max(arr[i], curSum + arr[i]);
        maxSum = max(maxSum, curSum);
    }
    cout << "Max subarray sum: " << maxSum << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int maxSum = arr[0], curSum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            curSum = Math.max(arr[i], curSum + arr[i]);
            maxSum = Math.max(maxSum, curSum);
        }
        System.out.println("Max subarray sum: " + maxSum);
    }
}
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum = cur_sum = arr[0]
for x in arr[1:]:
    cur_sum = max(x, cur_sum + x)
    max_sum = max(max_sum, cur_sum)
print("Max subarray sum:", max_sum)
#include <stdio.h>
int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int maxSum = arr[0], curSum = arr[0];
    for (int i = 1; i < 9; i++) {
        curSum = curSum + arr[i] > arr[i] ? curSum + arr[i] : arr[i];
        if (curSum > maxSum) maxSum = curSum;
    }
    printf("Max subarray sum: %d\n", maxSum);
    return 0;
}

Running Sum

It works by keeping a running current sum: at each element, decide whether extending the previous subarray is still better than starting a fresh subarray at the current element, keeping whichever running sum is larger as the best answer seen so far.

Example: Running Sum

#include <iostream>
using namespace std;
int main() {
    int arr[] = {2, -1, 3, -4, 5};
    int curSum = 0, best = arr[0];
    for (int i = 0; i < 5; i++) {
        curSum = (curSum > 0) ? curSum + arr[i] : arr[i];
        cout << "After index " << i << ": running sum = " << curSum << endl;
        best = max(best, curSum);
    }
    cout << "Best: " << best << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {2, -1, 3, -4, 5};
        int curSum = 0, best = arr[0];
        for (int i = 0; i < arr.length; i++) {
            curSum = (curSum > 0) ? curSum + arr[i] : arr[i];
            System.out.println("After index " + i + ": running sum = " + curSum);
            best = Math.max(best, curSum);
        }
        System.out.println("Best: " + best);
    }
}
arr = [2, -1, 3, -4, 5]
cur_sum, best = 0, arr[0]
for i, x in enumerate(arr):
    cur_sum = cur_sum + x if cur_sum > 0 else x
    print(f"After index {i}: running sum = {cur_sum}")
    best = max(best, cur_sum)
print("Best:", best)
#include <stdio.h>
int main() {
    int arr[] = {2, -1, 3, -4, 5};
    int curSum = 0, best = arr[0];
    for (int i = 0; i < 5; i++) {
        curSum = (curSum > 0) ? curSum + arr[i] : arr[i];
        printf("After index %d: running sum = %d\n", i, curSum);
        if (curSum > best) best = curSum;
    }
    printf("Best: %d\n", best);
    return 0;
}

Maximum Subarray Details

Beyond just the maximum value, Kadane's algorithm can be extended to track the exact start and end indexes of that best subarray, which is useful when you need to report not just the sum but which elements produced it.

Example: Maximum Subarray Details

#include <iostream>
using namespace std;
int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int maxSum = arr[0], curSum = arr[0], start = 0, bestStart = 0, bestEnd = 0;
    for (int i = 1; i < 9; i++) {
        if (curSum < 0) { curSum = arr[i]; start = i; } else curSum += arr[i];
        if (curSum > maxSum) { maxSum = curSum; bestStart = start; bestEnd = i; }
    }
    cout << "Sum: " << maxSum << " from index " << bestStart << " to " << bestEnd << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int maxSum = arr[0], curSum = arr[0], start = 0, bestStart = 0, bestEnd = 0;
        for (int i = 1; i < arr.length; i++) {
            if (curSum < 0) { curSum = arr[i]; start = i; } else curSum += arr[i];
            if (curSum > maxSum) { maxSum = curSum; bestStart = start; bestEnd = i; }
        }
        System.out.println("Sum: " + maxSum + " from index " + bestStart + " to " + bestEnd);
    }
}
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum = cur_sum = arr[0]
start = best_start = best_end = 0
for i in range(1, len(arr)):
    if cur_sum < 0:
        cur_sum, start = arr[i], i
    else:
        cur_sum += arr[i]
    if cur_sum > max_sum:
        max_sum, best_start, best_end = cur_sum, start, i
print(f"Sum: {max_sum} from index {best_start} to {best_end}")
#include <stdio.h>
int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int maxSum = arr[0], curSum = arr[0], start = 0, bestStart = 0, bestEnd = 0;
    for (int i = 1; i < 9; i++) {
        if (curSum < 0) { curSum = arr[i]; start = i; } else curSum += arr[i];
        if (curSum > maxSum) { maxSum = curSum; bestStart = start; bestEnd = i; }
    }
    printf("Sum: %d from index %d to %d\n", maxSum, bestStart, bestEnd);
    return 0;
}

Circular Array

For a circular array, where the subarray is allowed to wrap around from the end back to the beginning, the maximum circular sum equals the total array sum minus the minimum subarray sum (found using Kadane's the same way, just minimizing instead of maximizing).

Example: Circular Array

#include <iostream>
using namespace std;
int main() {
    int arr[] = {5, -3, 5};
    int total = 0, maxSum = arr[0], curMax = arr[0], minSum = arr[0], curMin = arr[0];
    for (int i = 0; i < 3; i++) {
        total += arr[i];
        curMax = max(arr[i], curMax + arr[i]); maxSum = max(maxSum, curMax);
        curMin = min(arr[i], curMin + arr[i]); minSum = min(minSum, curMin);
    }
    int maxCircular = (maxSum < 0) ? maxSum : max(maxSum, total - minSum);
    cout << "Max circular sum: " << maxCircular << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {5, -3, 5};
        int total = 0, maxSum = arr[0], curMax = arr[0], minSum = arr[0], curMin = arr[0];
        for (int x : arr) {
            total += x;
            curMax = Math.max(x, curMax + x); maxSum = Math.max(maxSum, curMax);
            curMin = Math.min(x, curMin + x); minSum = Math.min(minSum, curMin);
        }
        int maxCircular = (maxSum < 0) ? maxSum : Math.max(maxSum, total - minSum);
        System.out.println("Max circular sum: " + maxCircular);
    }
}
arr = [5, -3, 5]
total, cur_max, max_sum, cur_min, min_sum = 0, arr[0], arr[0], arr[0], arr[0]
for x in arr:
    total += x
    cur_max = max(x, cur_max + x); max_sum = max(max_sum, cur_max)
    cur_min = min(x, cur_min + x); min_sum = min(min_sum, cur_min)
max_circular = max_sum if max_sum < 0 else max(max_sum, total - min_sum)
print("Max circular sum:", max_circular)
#include <stdio.h>
int main() {
    int arr[] = {5, -3, 5};
    int total = 0, maxSum = arr[0], curMax = arr[0], minSum = arr[0], curMin = arr[0];
    for (int i = 0; i < 3; i++) {
        total += arr[i];
        curMax = (arr[i] > curMax + arr[i]) ? arr[i] : curMax + arr[i]; if (curMax > maxSum) maxSum = curMax;
        curMin = (arr[i] < curMin + arr[i]) ? arr[i] : curMin + arr[i]; if (curMin < minSum) minSum = curMin;
    }
    int maxCircular = (maxSum < 0) ? maxSum : (maxSum > total - minSum ? maxSum : total - minSum);
    printf("Max circular sum: %d\n", maxCircular);
    return 0;
}

Kadane's Practice

Kadane's algorithm underlies many 'maximum subarray'-style interview problems, but watch the edge cases carefully, especially arrays that are entirely negative, where the best answer is just the single largest (least negative) element.

Example: Kadane's Practice

#include <iostream>
using namespace std;
int main() {
    int arr[] = {-8, -3, -6, -2, -5, -4};
    int maxSum = arr[0], curSum = arr[0];
    for (int i = 1; i < 6; i++) {
        curSum = max(arr[i], curSum + arr[i]);
        maxSum = max(maxSum, curSum);
    }
    cout << "All-negative array best subarray sum: " << maxSum << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {-8, -3, -6, -2, -5, -4};
        int maxSum = arr[0], curSum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            curSum = Math.max(arr[i], curSum + arr[i]);
            maxSum = Math.max(maxSum, curSum);
        }
        System.out.println("All-negative array best subarray sum: " + maxSum);
    }
}
arr = [-8, -3, -6, -2, -5, -4]
max_sum = cur_sum = arr[0]
for x in arr[1:]:
    cur_sum = max(x, cur_sum + x)
    max_sum = max(max_sum, cur_sum)
print("All-negative array best subarray sum:", max_sum)
#include <stdio.h>
int main() {
    int arr[] = {-8, -3, -6, -2, -5, -4};
    int maxSum = arr[0], curSum = arr[0];
    for (int i = 1; i < 6; i++) {
        curSum = (arr[i] > curSum + arr[i]) ? arr[i] : curSum + arr[i];
        if (curSum > maxSum) maxSum = curSum;
    }
    printf("All-negative array best subarray sum: %d\n", maxSum);
    return 0;
}
🔒

Chapter Quiz — Complete all 8 topics to unlock

0/8 topics done

Complete these topics first:

← Previous Lesson Prefix Sum Next Lesson → Dutch National Flag

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.