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.