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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kadane's Algorithm on a simple array

What is the output of the following C++ code that uses Kadane's Algorithm to find the maximum subarray sum?

DSA C++

int maxSubArraySum(int arr[], int n) {
    int max_so_far = arr[0];
    int curr_max = arr[0];
    for (int i = 1; i < n; i++) {
        curr_max = std::max(arr[i], curr_max + arr[i]);
        max_so_far = std::max(max_so_far, curr_max);
    }
    return max_so_far;
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    std::cout << maxSubArraySum(arr, n);
    return 0;
}

A 6

B 7

C 5

D 4

💡 Hint

Trace the sum of subarrays and keep track of the maximum sum found so far.

Kadane's algorithm finds the maximum sum of a contiguous subarray. For the given array, the maximum sum subarray is [4, -1, 2, 1] which sums to 6.

❓ Predict Output

intermediate

Maximum subarray sum with all negative numbers

What will be the output of the Kadane's Algorithm implementation on the following array?

DSA C++

int maxSubArraySum(int arr[], int n) {
    int max_so_far = arr[0];
    int curr_max = arr[0];
    for (int i = 1; i < n; i++) {
        curr_max = std::max(arr[i], curr_max + arr[i]);
        max_so_far = std::max(max_so_far, curr_max);
    }
    return max_so_far;
}

int main() {
    int arr[] = {-8, -3, -6, -2, -5, -4};
    int n = sizeof(arr) / sizeof(arr[0]);
    std::cout << maxSubArraySum(arr, n);
    return 0;
}

A -4

B -3

C -2

D -5

💡 Hint

When all numbers are negative, the maximum subarray is the single largest number.

Kadane's algorithm returns the largest single element when all are negative. Here, -2 is the largest number.

🧠 Conceptual

advanced

Understanding Kadane's Algorithm variables

In Kadane's Algorithm, what does the variable 'curr_max' represent during the iteration?

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

B The sum of all elements in the array up to the current index

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

D The maximum sum of a subarray ending at the current index

💡 Hint

Think about how the algorithm decides whether to start a new subarray or continue the existing one.

'curr_max' holds the maximum sum of a subarray that ends exactly at the current index. It helps decide whether to extend the previous subarray or start fresh.

❓ Predict Output

advanced

Output of Kadane's Algorithm with zeroes included

What is the output of the following code using Kadane's Algorithm on the given array?

DSA C++

int maxSubArraySum(int arr[], int n) {
    int max_so_far = arr[0];
    int curr_max = arr[0];
    for (int i = 1; i < n; i++) {
        curr_max = std::max(arr[i], curr_max + arr[i]);
        max_so_far = std::max(max_so_far, curr_max);
    }
    return max_so_far;
}

int main() {
    int arr[] = {0, -3, 5, -2, 1, 0, -1, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    std::cout << maxSubArraySum(arr, n);
    return 0;
}

A 5

B 7

C 6

D 8

💡 Hint

Identify the subarray with the largest sum including zeroes.

The maximum subarray is [5, -2, 1, 0, -1, 4] which sums to 7.

🚀 Application

expert

Finding maximum subarray sum and its indices

Modify Kadane's Algorithm to also return the start and end indices of the maximum sum subarray. What will be the output for the array below?

DSA C++

std::tuple<int, int, int> maxSubArraySumWithIndices(int arr[], int n) {
    int max_so_far = arr[0];
    int curr_max = arr[0];
    int start = 0, end = 0, s = 0;
    for (int i = 1; i < n; i++) {
        if (arr[i] > curr_max + arr[i]) {
            curr_max = arr[i];
            s = i;
        } else {
            curr_max += arr[i];
        }
        if (curr_max > max_so_far) {
            max_so_far = curr_max;
            start = s;
            end = i;
        }
    }
    return {max_so_far, start, end};
}

int main() {
    int arr[] = {-1, 3, -2, 5, -3, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    auto [max_sum, start_idx, end_idx] = maxSubArraySumWithIndices(arr, n);
    std::cout << max_sum << " " << start_idx << " " << end_idx;
    return 0;
}

A 6 1 3

B 5 2 5

C 7 1 4

D 6 0 3

💡 Hint

Track the start index when you reset the current sum and update the max sum indices accordingly.

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

Practice

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

easy

A. The total sum of all elements

B. The minimum element in the array

C. The maximum product of any two 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 a contiguous subarray within a one-dimensional array of numbers.

2. Step 2: Compare options with the algorithm's purpose

   Options A, B, and D do not describe the main goal of Kadane's Algorithm. Only The maximum sum of a contiguous subarray correctly states it finds the maximum sum of a contiguous subarray.

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 finds max sum in a continuous slice [OK]

Common Mistakes:

• Confusing maximum sum with maximum product
• Thinking it finds minimum element
• Assuming it sums all elements

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

easy

A. int max_so_far = INT_MIN, max_ending_here = 0;

B. int max_so_far = INT_MAX, max_ending_here = INT_MAX;

C. int max_so_far = 0, max_ending_here = INT_MIN;

D. int max_so_far = 0, max_ending_here = 0;

Solution

1. Step 1: Understand variable roles in Kadane's Algorithm

   max_so_far stores the maximum sum found so far, so it should start very low (INT_MIN) to allow any sum to replace it. max_ending_here tracks the current subarray sum and starts at 0.

2. Step 2: Check each option's initialization

   int max_so_far = INT_MIN, max_ending_here = 0; correctly initializes max_so_far to INT_MIN and max_ending_here to 0. Other options either start max_so_far at 0 or INT_MAX, which can cause incorrect results.

3. Final Answer:

   int max_so_far = INT_MIN, max_ending_here = 0; -> Option A

4. Quick Check:

   max_so_far = INT_MIN, max_ending_here = 0 [OK]

Hint: Start max_so_far at INT_MIN to handle negatives [OK]

Common Mistakes:

• Initializing max_so_far to 0 causes wrong results with negatives
• Setting max_ending_here to INT_MIN breaks logic
• Using INT_MAX causes overflow issues

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

int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int n = 9;
int max_so_far = INT_MIN, max_ending_here = 0;
for (int i = 0; i < n; i++) {
    max_ending_here += arr[i];
    if (max_so_far < max_ending_here)
        max_so_far = max_ending_here;
    if (max_ending_here < 0)
        max_ending_here = 0;
}
std::cout << max_so_far << std::endl;

medium

A. 6

B. 7

C. 5

D. 4

Solution

1. Step 1: Trace Kadane's Algorithm on the array

   Iterate through arr: max_ending_here and max_so_far update as follows:
   - i=0: max_ending_here=-2, max_so_far=-2, reset max_ending_here=0
   - i=1: max_ending_here=1, max_so_far=1
   - i=2: max_ending_here=-2, max_so_far=1, reset max_ending_here=0
   - i=3: max_ending_here=4, max_so_far=4
   - i=4: max_ending_here=3, max_so_far=4
   - i=5: max_ending_here=5, max_so_far=5
   - i=6: max_ending_here=6, max_so_far=6
   - i=7: max_ending_here=1, max_so_far=6
   - i=8: max_ending_here=5, max_so_far=6

2. Step 2: Identify maximum subarray sum

   The maximum sum found is 6, which corresponds to subarray [4, -1, 2, 1].

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Max subarray sum = 6 [OK]

Hint: Add elements, reset sum if negative, track max [OK]

Common Mistakes:

• Not resetting max_ending_here when negative
• Confusing max_so_far with current sum
• Miscounting subarray sums

4. Identify the bug in this Kadane's Algorithm implementation and select the fix:

int maxSubArraySum(int arr[], int n) {
    int max_so_far = 0, max_ending_here = 0;
    for (int i = 0; i < n; i++) {
        max_ending_here += arr[i];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
        if (max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_so_far;
}

medium

A. Remove resetting max_ending_here to 0

B. Initialize max_ending_here to INT_MIN instead of 0

C. Initialize max_so_far to INT_MIN instead of 0

D. Change loop to start from i = 1

Solution

1. Step 1: Analyze initialization impact on negative arrays

   Starting max_so_far at 0 causes incorrect results if all array elements are negative, as max_so_far will never update to a negative sum.

2. Step 2: Fix initialization to handle all negative values

   Setting max_so_far to INT_MIN allows it to update correctly even if all elements are negative, ensuring the maximum subarray sum is found.

3. Final Answer:

   Initialize max_so_far to INT_MIN instead of 0 -> Option C

4. Quick Check:

   max_so_far = INT_MIN fixes negative-only arrays [OK]

Hint: Use INT_MIN for max_so_far to handle negatives [OK]

Common Mistakes:

• Leaving max_so_far at 0 causes wrong max for negatives
• Removing reset breaks algorithm logic
• Changing loop start misses first element

5. Given an array with all negative numbers: int arr[] = {-8, -3, -6, -2, -5, -4}; What is the maximum subarray sum using Kadane's Algorithm?

hard

A. 0

B. -2

C. -3

D. -8

Solution

1. Step 1: Understand Kadane's behavior with all negative numbers

   When all numbers are negative, resetting max_ending_here to 0 causes the algorithm to miss the largest (least negative) number. Proper initialization with max_so_far = INT_MIN helps track the max single element.

2. Step 2: Identify the maximum single element

   The largest number in the array is -2, which is the maximum subarray sum since any longer subarray sum will be smaller.

3. Final Answer:

   -2 -> Option B

4. Quick Check:

   Max single negative element = -2 [OK]

Hint: Max subarray in negatives is max single element [OK]

Common Mistakes:

• Assuming max sum is 0 by resetting sums
• Ignoring single element max in negative arrays
• Confusing minimum with maximum