Kadane's Algorithm Maximum Subarray in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kadane's Algorithm on a Mixed Array

What is the output of the following Java code that uses Kadane's algorithm to find the maximum subarray sum?

DSA Java

public class Main {
    public static int maxSubArray(int[] nums) {
        int maxSoFar = nums[0];
        int maxEndingHere = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }

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

A 5

B 7

C 6

D 4

💡 Hint

Think about the largest sum of a continuous subarray.

Kadane's algorithm finds the maximum sum of a contiguous subarray. Here, the maximum sum is 6 from subarray [4, -1, 2, 1].

🧠 Conceptual

intermediate

Understanding Kadane's Algorithm Variables

In Kadane's algorithm, what does the variable 'maxEndingHere' represent during the iteration?

A The maximum sum of any subarray found so far in the entire array.

B The maximum sum of a subarray ending at the current index.

C The minimum sum of a subarray ending at the current index.

D The sum of all elements processed so far.

💡 Hint

Focus on the subarray that ends exactly at the current position.

'maxEndingHere' keeps track of the maximum sum of a subarray that ends exactly at the current index, helping to decide whether to extend the previous subarray or start fresh.

❓ Predict Output

advanced

Output with All Negative Numbers

What will be the output of the following Java code using Kadane's algorithm on an array with all negative numbers?

DSA Java

public class Main {
    public static int maxSubArray(int[] nums) {
        int maxSoFar = nums[0];
        int maxEndingHere = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }

    public static void main(String[] args) {
        int[] nums = {-8, -3, -6, -2, -5, -4};
        System.out.println(maxSubArray(nums));
    }
}

A 0

B -8

C -28

D -2

💡 Hint

Kadane's algorithm returns the largest single element if all are negative.

When all numbers are negative, the maximum subarray is the single largest number, which is -2 here.

🔧 Debug

advanced

Identify the Bug in Kadane's Algorithm Implementation

What error will occur when running this Java code for Kadane's algorithm?

DSA Java

public class Main {
    public static int maxSubArray(int[] nums) {
        int maxSoFar = 0;
        int maxEndingHere = 0;
        for (int i = 0; i < nums.length; i++) {
            maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }

    public static void main(String[] args) {
        int[] nums = {-1, -2, -3, -4};
        System.out.println(maxSubArray(nums));
    }
}

A Returns 0, which is incorrect for all negative input

B Returns the correct maximum subarray sum -1

C Throws NullPointerException

D Throws ArrayIndexOutOfBoundsException

💡 Hint

Check initial values of maxSoFar and maxEndingHere for negative arrays.

Initializing maxSoFar and maxEndingHere to 0 causes the algorithm to return 0 even when all numbers are negative, which is incorrect.

🚀 Application

expert

Maximum Subarray Sum with Indices

Modify Kadane's algorithm to also return the start and end indices of the maximum subarray. What will be the output for the array [1, -2, 3, 5, -1, 2]?

DSA Java

public class Main {
    public static int[] maxSubArrayWithIndices(int[] nums) {
        int maxSoFar = nums[0];
        int maxEndingHere = nums[0];
        int start = 0, end = 0, s = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > maxEndingHere + nums[i]) {
                maxEndingHere = nums[i];
                s = i;
            } else {
                maxEndingHere += nums[i];
            }
            if (maxEndingHere > maxSoFar) {
                maxSoFar = maxEndingHere;
                start = s;
                end = i;
            }
        }
        return new int[]{maxSoFar, start, end};
    }

    public static void main(String[] args) {
        int[] nums = {1, -2, 3, 5, -1, 2};
        int[] result = maxSubArrayWithIndices(nums);
        System.out.println("Max Sum: " + result[0] + ", Start: " + result[1] + ", End: " + result[2]);
    }
}

A Max Sum: 9, Start: 2, End: 5

B Max Sum: 6, Start: 1, End: 5

C Max Sum: 7, Start: 0, End: 3

D Max Sum: 8, Start: 2, End: 4

💡 Hint

Track start index when resetting maxEndingHere.

The maximum subarray is [3, 5, -1, 2] with sum 9, starting at index 2 and ending at index 5.

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