Kadane's Algorithm Maximum Subarray in DSA Java - Execution Trace

Concept Flow - Kadane's Algorithm Maximum Subarray

Start with first element

↓

Initialize current_sum and max_sum

↓

For each next element

↓

Update current_sum = max(element, current_sum + element)

↓

Update max_sum = max(max_sum, current_sum)

↓

Repeat until end of array

↓

Return max_sum as max subarray sum

Kadane's algorithm scans the array once, updating current and maximum sums to find the largest sum of any continuous subarray.

Execution Sample

DSA Java

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;
}

This code finds the maximum sum of a continuous subarray in the given integer array.

Execution Table

Step	Index i	Current Element nums[i]	Current Sum	Max Sum	Explanation
1	0	-2	-2	-2	Initialize currentSum and maxSum with first element -2
2	1	1	max(1, -2 + 1) = 1	max(-2, 1) = 1	Start loop: currentSum updated to 1, maxSum updated to 1
3	2	-3	max(-3, 1 + (-3)) = max(-3, -2) = -2	max(1, -2) = 1	currentSum becomes -2, maxSum stays 1
4	3	4	max(4, -2 + 4) = max(4, 2) = 4	max(1, 4) = 4	currentSum updated to 4, maxSum updated to 4
5	4	-1	max(-1, 4 + (-1)) = max(-1, 3) = 3	max(4, 3) = 4	currentSum is 3, maxSum stays 4
6	5	2	max(2, 3 + 2) = max(2, 5) = 5	max(4, 5) = 5	currentSum updated to 5, maxSum updated to 5
7	6	1	max(1, 5 + 1) = max(1, 6) = 6	max(5, 6) = 6	currentSum updated to 6, maxSum updated to 6
8	7	-5	max(-5, 6 + (-5)) = max(-5, 1) = 1	max(6, 1) = 6	currentSum becomes 1, maxSum stays 6
9	8	4	max(4, 1 + 4) = max(4, 5) = 5	max(6, 5) = 6	currentSum updated to 5, maxSum stays 6
10	End	-	-	6	Reached end of array, maxSum 6 is the maximum subarray sum

💡 Loop ends after last element; maxSum holds the maximum subarray sum.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	Final
currentSum	-2	1	-2	4	3	5	6	1	5	5
maxSum	-2	1	1	4	4	5	6	6	6	6
i	0	1	2	3	4	5	6	7	8	End

Key Moments - 3 Insights

Why do we compare nums[i] with currentSum + nums[i] when updating currentSum?

Because starting fresh from nums[i] might give a larger sum than continuing the previous subarray. See execution_table steps 2 and 4 where currentSum resets to nums[i].

Why does maxSum sometimes stay the same even when currentSum changes?

maxSum only updates if currentSum is greater. For example, at step 5 currentSum is 3 but maxSum remains 4 because 4 is larger (see execution_table).

What happens if all numbers are negative?

Kadane's algorithm still works by initializing currentSum and maxSum to the first element. It picks the largest single element as maxSum (see step 1).

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What is the currentSum value?

A 4

B -2

C 3

D 1

💡 Hint

Check the 'Current Sum' column at step 4 in the execution_table.

At which step does maxSum first become 5?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the 'Max Sum' column in execution_table and find when it changes to 5.

If the array started with a larger positive number at index 0, how would currentSum change at step 1?

A It would be that larger number

B It would be zero

C It would be negative

D It would be the sum of first two elements

💡 Hint

currentSum initializes to nums[0], see variable_tracker and execution_table step 1.

Concept Snapshot

Kadane's Algorithm finds max sum of continuous subarray.
Initialize currentSum and maxSum with first element.
For each element, update currentSum = max(element, currentSum + element).
Update maxSum = max(maxSum, currentSum).
Return maxSum after full array scan.

Full Transcript

Kadane's algorithm scans the array once to find the maximum sum of any continuous subarray. It starts by setting currentSum and maxSum to the first element. Then for each next element, it updates currentSum to be the larger of the current element alone or the current element plus the previous currentSum. This decides whether to start a new subarray or continue the old one. After updating currentSum, it updates maxSum if currentSum is larger. This process repeats until the end of the array. The final maxSum is the maximum subarray sum. The execution table shows each step with currentSum and maxSum values. Key moments clarify why we compare current element alone versus adding to currentSum, why maxSum sometimes stays the same, and how the algorithm works with all negative numbers.

Practice

1. What does Kadane's Algorithm primarily help to find in an array of integers?

easy

A. The minimum element in the array

B. The number of positive elements

C. The total sum of all elements

D. The maximum sum of a contiguous subarray

Solution

1. Step 1: Understand the problem Kadane's Algorithm solves

   Kadane's Algorithm is designed to find the maximum sum of any contiguous subarray within a given array.

2. Step 2: Differentiate from other array operations

   It does not find minimum elements, total sum, or count positives, but specifically the maximum sum of a continuous segment.

3. Final Answer:

   The maximum sum of a contiguous subarray -> Option D

4. Quick Check:

   Maximum subarray sum = maximum sum of contiguous elements [OK]

Hint: Kadane's finds max sum of continuous elements fast [OK]

Common Mistakes:

• Confusing maximum subarray sum with total array sum
• Thinking it finds minimum or count of elements
• Assuming it works on non-contiguous elements

2. Which of the following is the correct initialization for Kadane's Algorithm variables in Java?

easy

A. int maxSoFar = 0, maxEndingHere = 0;

B. int maxSoFar = 0, maxEndingHere = Integer.MAX_VALUE;

C. int maxSoFar = Integer.MIN_VALUE, maxEndingHere = 0;

D. int maxSoFar = Integer.MAX_VALUE, maxEndingHere = Integer.MIN_VALUE;

Solution

1. Step 1: Identify correct initial values for Kadane's variables

   maxSoFar should start at the smallest integer to handle all negative arrays; maxEndingHere starts at 0 to accumulate sums.

2. Step 2: Check each option's initialization

   int maxSoFar = Integer.MIN_VALUE, maxEndingHere = 0; correctly sets maxSoFar to Integer.MIN_VALUE and maxEndingHere to 0, which is standard practice.

3. Final Answer:

   int maxSoFar = Integer.MIN_VALUE, maxEndingHere = 0; -> Option C

4. Quick Check:

   Initialize maxSoFar low, maxEndingHere zero [OK]

Hint: Start maxSoFar at smallest int, maxEndingHere at zero [OK]

Common Mistakes:

• Initializing maxSoFar to 0 causes errors with all negative arrays
• Swapping maxSoFar and maxEndingHere initial values
• Using Integer.MAX_VALUE incorrectly

3. What is the output of the following Java code using Kadane's Algorithm?

int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int maxSoFar = Integer.MIN_VALUE, maxEndingHere = 0;
for (int num : arr) {
    maxEndingHere += num;
    if (maxSoFar < maxEndingHere) maxSoFar = maxEndingHere;
    if (maxEndingHere < 0) maxEndingHere = 0;
}
System.out.println(maxSoFar);

medium

A. 6

B. 7

C. 5

D. 4

Solution

1. Step 1: Trace the loop and update sums

   Iterate through arr, updating maxEndingHere and maxSoFar:
   - Start: maxSoFar = -∞, maxEndingHere = 0
   - Add -2: maxEndingHere = -2 (reset to 0)
   - Add 1: maxEndingHere = 1, maxSoFar = 1
   - Add -3: maxEndingHere = -2 (reset to 0)
   - Add 4: maxEndingHere = 4, maxSoFar = 4
   - Add -1: maxEndingHere = 3
   - Add 2: maxEndingHere = 5, maxSoFar = 5
   - Add 1: maxEndingHere = 6, maxSoFar = 6
   - Add -5: maxEndingHere = 1
   - Add 4: maxEndingHere = 5

2. Step 2: Identify maximum sum found

   The maximum sum recorded is 6, but check carefully:
   At step adding 1 after 2, maxEndingHere = 6, maxSoFar = 6
   At last step, maxEndingHere = 5, maxSoFar remains 6
   Wait, re-check:
   Actually, after adding 1 (step 7), maxEndingHere = 6
   Then adding -5 (step 8), maxEndingHere = 1
   Then adding 4 (step 9), maxEndingHere = 5
   So maxSoFar = 6

3. Correction:

   Re-examining the sums, the maximum subarray is [4, -1, 2, 1] which sums to 6, but the subarray [4, -1, 2, 1] sums to 6, so 6 is correct.
   However, the standard Kadane's algorithm for this array returns 6, but the known maximum subarray sum is 6.
   But the options include 7, which is incorrect.
   Therefore, the original answer C (6) is correct.

4. Final Answer:

   6 -> Option A

5. Quick Check:

   Max subarray sum = 6 [OK]

Hint: Add and reset sum; track max sum found [OK]

Common Mistakes:

• Forgetting to reset maxEndingHere when negative
• Miscounting sums during iteration
• Confusing maxSoFar with maxEndingHere

4. Identify the bug in this Kadane's Algorithm Java code snippet:

int maxSoFar = 0, maxEndingHere = 0;
for (int num : arr) {
    maxEndingHere = Math.max(num, maxEndingHere + num);
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
System.out.println(maxSoFar);

medium

A. maxEndingHere should be initialized to Integer.MAX_VALUE

B. maxSoFar should start at Integer.MIN_VALUE, not 0

C. The loop should start from index 1, not 0

D. Using Math.max is incorrect for Kadane's Algorithm

Solution

1. Step 1: Analyze initialization of maxSoFar

   Starting maxSoFar at 0 causes incorrect results if all numbers are negative, as maxSoFar will never update to a negative max subarray.

2. Step 2: Correct initialization for negative arrays

   maxSoFar should be initialized to Integer.MIN_VALUE to correctly track maximum sums even if all are negative.

3. Final Answer:

   maxSoFar should start at Integer.MIN_VALUE, not 0 -> Option B

4. Quick Check:

   Initialize maxSoFar low to handle negatives [OK]

Hint: Initialize maxSoFar to smallest int to handle negatives [OK]

Common Mistakes:

• Initializing maxSoFar to 0 causes wrong max for negative arrays
• Misunderstanding Math.max usage in Kadane's
• Incorrect loop indexing assumptions

5. Given an array int[] arr = {-1, -2, -3, -4}, what will Kadane's Algorithm return as the maximum subarray sum if initialized with maxSoFar = Integer.MIN_VALUE and maxEndingHere = 0?

hard

A. -1

B. 0

C. -10

D. 4

Solution

1. Step 1: Trace Kadane's Algorithm on all negative array

   maxEndingHere resets to 0 when negative, but maxSoFar tracks max subarray sum:
   - Add -1: maxEndingHere = -1 (reset to 0), maxSoFar = -1
   - Add -2: maxEndingHere = -2 (reset to 0), maxSoFar = -1
   - Add -3: maxEndingHere = -3 (reset to 0), maxSoFar = -1
   - Add -4: maxEndingHere = -4 (reset to 0), maxSoFar = -1

2. Step 2: Identify maximum subarray sum

   The maximum subarray sum is -1, the largest single element in the array.

3. Final Answer:

   -1 -> Option A

4. Quick Check:

   Max subarray sum in negatives = max single element [OK]

Hint: Max sum in all negatives is largest single element [OK]

Common Mistakes:

• Assuming max sum is 0 due to resets
• Summing all negatives incorrectly
• Ignoring initialization of maxSoFar