Start practising

Kadane's Algorithm - Simple

Medium Arrays & Hashing Kadane's Algorithm Original on GeeksforGeeks

Kadane's Algorithm - Simple is a medium arrays & hashing problem solved with the kadane's algorithm pattern. The best approach, optimal (kadane's algorithm), runs in O(n) time and O(1) space. Below are 2 approaches in Java, from brute force up.

Problem

Given an integer array arr, find the largest sum of any non-empty contiguous subarray.

Examples

Example 1

Input
arr = [2, -4, 3, -1, 2, -5, 4]
Output
4
Why
The subarray [3, -1, 2] sums to 4.

Example 2

Input
arr = [-3, -1, -2]
Output
-1
Why
All values are negative, so the best subarray is the single largest element.

Constraints

  • 1 <= arr.length <= 10^5
  • -10^4 <= arr[i] <= 10^4
  • The subarray must contain at least one element.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Brute forceO(n²)O(1)
Optimal (Kadane's algorithm)O(n)O(1)

1Brute force

TimeO(n²)All n(n + 1) / 2 subarrays are summed incrementally.
SpaceO(1)

Try every start index and extend to every end index, keeping a running sum and the best seen.

  1. For each i, reset sum = 0.
  2. For each j from i, add arr[j] and update best.
Java
class Solution {
    long maxSubarraySum(int[] arr) {
        long best = Long.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            long sum = 0;
            for (int j = i; j < arr.length; j++) {
                sum += arr[j];
                best = Math.max(best, sum);
            }
        }
        return best;
    }
}

2Optimal (Kadane's algorithm)

TimeO(n)One pass.
SpaceO(1)Two variables.

The best subarray ending at index i either extends the best subarray ending at i - 1 or starts fresh at i. Start fresh whenever the carried sum is negative.

  1. cur = best = arr[0].
  2. For each next x: cur = max(x, cur + x).
  3. best = max(best, cur).
Java
class Solution {
    long maxSubarraySum(int[] arr) {
        long cur = arr[0], best = arr[0];
        for (int i = 1; i < arr.length; i++) {
            cur = Math.max(arr[i], cur + arr[i]);
            best = Math.max(best, cur);
        }
        return best;
    }
}

Edge cases to test

  • All negative numbers
  • Single element
  • The whole array is the best subarray

Hints

Hint 1

If the running sum ending at the previous index is negative, is it worth carrying forward?

FAQ

What is the best time complexity for Kadane's Algorithm - Simple?

Optimal (Kadane's algorithm) runs in O(n) time and O(1) extra space. One pass.

Which pattern does Kadane's Algorithm - Simple use?

It is a arrays & hashing problem that uses the kadane's algorithm pattern. Other problems with the same pattern: Find minimum subarray sum, Kadane's Algo - Circular Array - No Extra Space.

Is there a brute force solution for Kadane's Algorithm - Simple?

Yes. Brute force takes O(n²) time and O(1) space. Try every start index and extend to every end index, keeping a running sum and the best seen.

Which edge cases should I test for Kadane's Algorithm - Simple?

All negative numbers; Single element; The whole array is the best subarray.