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

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of Kadane's algorithm on this array?

Given the array int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};, what is the maximum subarray sum found by Kadane's algorithm?

DSA C

int maxSubArraySum(int arr[], int size) {
    int max_so_far = arr[0];
    int curr_max = arr[0];
    for (int i = 1; i < size; i++) {
        curr_max = (arr[i] > curr_max + arr[i]) ? arr[i] : curr_max + arr[i];
        max_so_far = (max_so_far > curr_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]);
    int max_sum = maxSubArraySum(arr, n);
    printf("%d", max_sum);
    return 0;
}

A 4

B 7

C 5

D 6

💡 Hint

Think about the contiguous subarray with the largest sum.

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

❓ Predict Output

intermediate

What is the maximum subarray sum for all negative numbers?

Consider the array int arr[] = {-8, -3, -6, -2, -5, -4};. What does Kadane's algorithm return as the maximum subarray sum?

DSA C

int maxSubArraySum(int arr[], int size) {
    int max_so_far = arr[0];
    int curr_max = arr[0];
    for (int i = 1; i < size; i++) {
        curr_max = (arr[i] > curr_max + arr[i]) ? arr[i] : curr_max + arr[i];
        max_so_far = (max_so_far > curr_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]);
    int max_sum = maxSubArraySum(arr, n);
    printf("%d", max_sum);
    return 0;
}

A -3

B -2

C -4

D -5

💡 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 element. Here, -2 is the largest number.

🔧 Debug

advanced

Identify the bug in this Kadane's algorithm implementation

What error does this code produce when run on int arr[] = {-8, -3, -6, -2, -5, -4};?

DSA C

int maxSubArraySum(int arr[], int size) {
    int max_so_far = 0;
    int curr_max = 0;
    for (int i = 0; i < size; i++) {
        curr_max += arr[i];
        if (curr_max < 0)
            curr_max = 0;
        if (max_so_far < curr_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]);
    int max_sum = maxSubArraySum(arr, n);
    printf("%d", max_sum);
    return 0;
}

A Returns 0, which is incorrect

B Returns -2, which is correct

C Returns -8, which is incorrect

D Compilation error due to missing return

💡 Hint

Check how max_so_far and curr_max are initialized and updated.

This implementation resets curr_max to 0 when negative, which fails if all numbers are negative. It returns 0 instead of the correct -2.

🧠 Conceptual

advanced

What does Kadane's algorithm track during iteration?

Which two values does Kadane's algorithm maintain while scanning the array to find the maximum subarray sum?

A Current subarray sum and maximum subarray sum so far

B Minimum element and maximum element in the array

C Sum of all elements and length of the array

D Index of first and last elements of the array

💡 Hint

Think about what changes as you move through the array.

Kadane's algorithm keeps track of the current subarray sum (which may reset) and the maximum sum found so far to find the maximum contiguous sum.

🚀 Application

expert

Find the maximum subarray sum and its indices

Modify Kadane's algorithm to also return the start and end indices of the maximum sum subarray for int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};. What are the start and end indices of the maximum subarray?

DSA C

void maxSubArraySumWithIndices(int arr[], int size, int *max_sum, int *start, int *end) {
    int curr_max = arr[0];
    int max_so_far = arr[0];
    int s = 0;
    *start = 0;
    *end = 0;
    for (int i = 1; i < size; 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;
        }
    }
    *max_sum = max_so_far;
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    int max_sum, start, end;
    maxSubArraySumWithIndices(arr, n, &max_sum, &start, &end);
    printf("Max sum: %d, Start index: %d, End index: %d", max_sum, start, end);
    return 0;
}

A Max sum: 7, Start index: 2, End index: 6

B Max sum: 6, Start index: 2, End index: 5

C Max sum: 6, Start index: 3, End index: 6

D Max sum: 5, Start index: 3, End index: 7

💡 Hint

Track the start index when resetting current max sum.

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

Practice

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

easy

A. The total sum of all elements

B. The minimum element in the array

C. The maximum sum of a contiguous subarray

D. The maximum product of any two elements

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 with other options

   Options B, C, and D describe different problems unrelated to Kadane's Algorithm.

3. Final Answer:

   The maximum sum of a contiguous subarray -> Option C

4. Quick Check:

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

Hint: Kadane finds max sum in continuous parts of array [OK]

Common Mistakes:

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

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

easy

A. int max_so_far = INT_MIN, max_ending_here = 0;

B. int max_so_far = 0, max_ending_here = 0;

C. int max_so_far = 0, max_ending_here = INT_MIN;

D. int max_so_far = NULL, max_ending_here = 0;

Solution

1. Step 1: Understand initialization in Kadane's Algorithm

   We initialize max_so_far to the smallest integer (INT_MIN) to handle arrays with all negative numbers correctly, and max_ending_here to 0 to start accumulating sums.

2. Step 2: Evaluate each option

   int max_so_far = 0, max_ending_here = 0; initializes max_so_far to 0, which fails for all negative arrays. int max_so_far = 0, max_ending_here = INT_MIN; incorrectly initializes max_ending_here to INT_MIN. int max_so_far = NULL, max_ending_here = 0; uses NULL which is invalid for int.

3. Final Answer:

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

4. Quick Check:

   Use INT_MIN for max_so_far to handle negatives [OK]

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

Common Mistakes:

• Initializing max_so_far to 0 causes wrong results
• Using NULL for integer variables
• Swapping initial values of variables

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

int arr[] = {-2, 3, 2, -1};
int n = 4;
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;
}
printf("%d", max_so_far);

medium

A. 4

B. 5

C. 3

D. -1

Solution

1. Step 1: Trace the loop and update sums

   Iteration 0: max_ending_here = 0 + (-2) = -2; max_so_far = max(INT_MIN, -2) = -2; max_ending_here < 0, reset to 0.
   Iteration 1: max_ending_here = 0 + 3 = 3; max_so_far = max(-2, 3) = 3; max_ending_here >= 0, no reset.
   Iteration 2: max_ending_here = 3 + 2 = 5; max_so_far = max(3, 5) = 5; max_ending_here >= 0, no reset.
   Iteration 3: max_ending_here = 5 + (-1) = 4; max_so_far = max(5, 4) = 5; max_ending_here >= 0, no reset.

2. Step 2: Final max_so_far value

   After loop ends, max_so_far is 5, which is the maximum subarray sum.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Max subarray sum = 5 [OK]

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

Common Mistakes:

• Not resetting max_ending_here when negative
• Confusing max_so_far with current sum
• Incorrectly summing non-contiguous elements

4. Identify the bug in this Kadane's Algorithm implementation in C:

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. max_so_far should be initialized to INT_MIN

B. max_ending_here should be initialized to INT_MIN

C. Loop should start from i = 1

D. Return statement should return max_ending_here

Solution

1. Step 1: Analyze initialization of max_so_far

   Initializing max_so_far to 0 fails when all array elements are negative, as max_so_far will never update to a negative number.

2. Step 2: Correct initialization and effect

   Setting max_so_far to INT_MIN ensures the algorithm correctly finds the maximum subarray sum even if all numbers are negative.

3. Final Answer:

   max_so_far should be initialized to INT_MIN -> Option A

4. Quick Check:

   Use INT_MIN for max_so_far to handle negative arrays [OK]

Hint: Initialize max_so_far to INT_MIN for negative arrays [OK]

Common Mistakes:

• Initializing max_so_far to 0 causes wrong max for negatives
• Changing loop start index unnecessarily
• Returning wrong variable

5. Given an array int arr[] = {-3, -2, -1, -4}, what is the maximum subarray sum using Kadane's Algorithm?

hard

A. -3

B. 0

C. -10

D. -1

Solution

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

   When all numbers are negative, resetting max_ending_here to 0 loses the maximum negative number. Proper Kadane's initialization with max_so_far = INT_MIN helps track the largest negative number.

2. Step 2: Trace the array values

   max_so_far starts at INT_MIN.
   i=0: max_ending_here = -3; max_so_far = -3; reset max_ending_here to 0 since negative.
   i=1: max_ending_here = -2; max_so_far = max(-3, -2) = -2; reset max_ending_here to 0.
   i=2: max_ending_here = -1; max_so_far = max(-2, -1) = -1; reset max_ending_here to 0.
   i=3: max_ending_here = -4; max_so_far = max(-1, -4) = -1; reset max_ending_here to 0.

3. Final Answer:

   -1 -> Option D

4. Quick Check:

   Max negative number = -1 [OK]

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

Common Mistakes:

• Returning 0 instead of max negative
• Not handling all negative arrays
• Assuming sum must be positive