Find the Maximum-Sum Contiguous Subarray (Kadane's Algorithm) - Java

Category: Medium | Concepts used: Dynamic programming intuition, single-pass tracking

---

Problem Statement

Given an array of integers (which may include negative numbers), find the contiguous subarray with the largest sum, and return that sum.

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

Examples (with edge scenarios)

#	Input	Output	Why
1	[-2, 1, -3, 4, -1, 2, 1, -5, 4]	6	Best subarray is [4, -1, 2, 1]
2	[1, 2, 3, 4] (all positive)	10	The entire array is the best subarray
3	[-1, -2, -3] (all negative)	-1	Best “subarray” is just the single largest (least negative) element
4	[5] (single element)	5	Trivially, the only possible subarray
5	[] (empty)	Undefined / needs clarification	No subarray exists — clarify expected behavior with the interviewer

Common Fresher Mistake

Mistake	What happens	Fix
Assuming the answer is always non-negative (initializing maxSum = 0)	Fails on all-negative arrays (e.g., [-1,-2,-3] should give -1, not 0)	Initialize maxSum with the first element, not 0
Using brute force checking all O(n²) subarrays without knowing about Kadane’s algorithm	Correct but slow — O(n²) or worse, not what’s expected for this classic problem	Learn and apply Kadane’s algorithm — it’s a “must-know” pattern

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm whether the array may be null or empty, whether duplicates and original order matter, whether the method may modify the input, and whether the answer should contain values or original indices. These choices can change both the code and the best data structure.

Analogy: Venture Capitalist Funding (Carrying Debt)

Imagine you are starting a sequence of business ventures (the numbers in the array) over several consecutive years:

• Positive numbers represent profitable years; negative numbers represent years with massive debt losses.
• You are walking down the years:
  • maxEndingHere (Current business line): You have a running business line. Every year, you decide:
    • Should you carry forward your accumulated balance sheet (debt/profits) and add the current year’s result?
    • Or is your accumulated debt so high (maxEndingHere + arr[i] < arr[i]) that it’s smarter to file for bankruptcy, wipe your balance sheet clean, and start a brand-new business fresh from this year’s venture (arr[i]) alone?
  • maxSoFar (All-time Record): You keep a record book of the highest net balance sheet your company ever achieved at any point in its history.
• Discarding a negative running sum is like closing down a failing business and starting fresh. By doing this, you ensure you never carry historical debt that drags down your future potential!

---

Solution 1 — Brute Force (Check All Subarrays)

Intuition

The most literal way to “find the best subarray” is to actually generate every possible contiguous subarray, compute each one’s sum, and keep track of the maximum seen so far.

public class MaxSubarrayBruteForce {
    public static int maxSubArraySum(int[] arr) {
        int maxSum = arr[0]; // start with first element, not 0

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

public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArraySum(arr)); // 6
    }
}

Output:

6

Dry Run (arr = [-2, 1, -3])

i=0: currentSum=-2 -> maxSum=max(-2,-2)=-2
     currentSum=-2+1=-1 -> maxSum=max(-2,-1)=-1
     currentSum=-1+(-3)=-4 -> maxSum=max(-1,-4)=-1
i=1: currentSum=1 -> maxSum=max(-1,1)=1
     currentSum=1+(-3)=-2 -> maxSum=max(1,-2)=1
i=2: currentSum=-3 -> maxSum=max(1,-3)=1

Final: maxSum=1  (best subarray is just [1])

Interviewer’s take

This works, but is O(n²) — way too slow for large arrays, and this is one of the most well-known interview problems specifically designed to test whether you know the O(n) optimization (Kadane’s algorithm). Offering only this solution is a strong signal you haven’t seen this classic problem before.

Follow-up questions you might get:

• “Can you solve this in O(n)?” → leads to Solution 2 (Kadane’s algorithm).

---

Solution 2 — Kadane’s Algorithm (O(n), Recommended)

Intuition

At each position, ask a simple question: “should I extend the current running subarray by including this next element, or is the running sum so damaging that it’s better to just start fresh from this element alone?” If the running sum ever drops below the value of the current element itself, it means the “prefix” we were carrying was actively hurting us — better to discard it and restart. Track the best sum seen at any point along the way.

public class MaxSubarrayKadane {
    public static int maxSubArraySum(int[] arr) {
        int maxEndingHere = arr[0]; // best sum of a subarray ENDING at current position
        int maxSoFar = arr[0];       // best sum found anywhere so far

for (int i = 1; i < arr.length; i++) {
            // either extend the previous subarray, or start fresh at arr[i]
            maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }

public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArraySum(arr)); // 6

int[] allNegative = {-1, -2, -3};
        System.out.println(maxSubArraySum(allNegative)); // -1
    }
}

Output:

6
-1

Dry Run (arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4])

Start: maxEndingHere=-2, maxSoFar=-2

i=1(1):  maxEndingHere=max(1, -2+1=-1)=1     | maxSoFar=max(-2,1)=1
i=2(-3): maxEndingHere=max(-3, 1-3=-2)=-2     | maxSoFar=max(1,-2)=1
i=3(4):  maxEndingHere=max(4, -2+4=2)=4       | maxSoFar=max(1,4)=4
i=4(-1): maxEndingHere=max(-1, 4-1=3)=3       | maxSoFar=max(4,3)=4
i=5(2):  maxEndingHere=max(2, 3+2=5)=5        | maxSoFar=max(4,5)=5
i=6(1):  maxEndingHere=max(1, 5+1=6)=6        | maxSoFar=max(5,6)=6
i=7(-5): maxEndingHere=max(-5, 6-5=1)=1       | maxSoFar=max(6,1)=6
i=8(4):  maxEndingHere=max(4, 1+4=5)=5        | maxSoFar=max(6,5)=6

Final: maxSoFar=6  (matches expected answer, corresponding to subarray [4,-1,2,1])

Interviewer’s take

This is the gold-standard answer for this problem — O(n) time, O(1) space, and it’s a specifically named, famous algorithm (“Kadane’s Algorithm”) that interviewers expect candidates to know or derive. The core insight — “extend or restart” — is a foundational dynamic programming pattern that shows up in many other problems too.

Follow-up questions you might get:

• “Why does ‘restart if maxEndingHere would be smaller than arr[i] alone’ work correctly?” → If the running sum ever becomes a net negative drag, carrying it forward can only ever hurt future sums — so it’s always at least as good (often better) to abandon it and start counting fresh from the current element.
• “How would you also return the actual subarray (not just the sum)?” → Track the start/end indices whenever maxSoFar gets updated, alongside the sum itself.
• “What if the array is empty?” → Should be handled explicitly (e.g., throw an exception or return a sentinel value) — clarify expected behavior with the interviewer.

---

📊 Visual Flowchart

graph TD
    Start["Input: Array arr"] --> Init["maxEndingHere = arr[0]<br>maxSoFar = arr[0]<br>i = 1"]
    Init --> Loop{"i < arr.length?"}
    Loop -->|Yes| Decide{"Extend or Restart?<br>maxEndingHere = max(arr[i], maxEndingHere + arr[i])"}
    Decide --> Record{"Update Record?<br>maxSoFar = max(maxSoFar, maxEndingHere)"}
    Record --> Next["i++"]
    Next --> Loop
    Loop -->|No| End["Return maxSoFar"]

---

Final Verdict — Which Solution Should You Give?

Solution 1 (brute force)  ──O(n²)──►  Only good as a starting point, will be asked to optimize
Solution 2 (Kadane's Algorithm)  ──O(n)──►   THE EXPECTED, CLASSIC ANSWER

• Solution 2 (Kadane’s algorithm) is essential to know — this is one of the most frequently asked array problems in interviews, and the O(n) solution is considered the baseline expectation, not a bonus.

---

Quick Recap

Approach	Time	Space	Interview Signal
Brute force (all subarrays)	O(n²)	O(1)	Shows correctness understanding, but expected to be improved
Kadane’s Algorithm	O(n)	O(1)	Expected, classic optimal solution