Tag contiguous subarray

Maximum Subarray Sum – Kadane’s Algorithm in C: A Comprehensive Tutorial

Finding the maximum subarray sum is one of the most fundamental problems in algorithm design. Given an integer array, the task is to find the contiguous subarray (containing at least one element) with the maximum sum. This problem is elegantly solved by Kadane’s Algorithm in O(n) time, making it a favorite in coding interviews and a cornerstone of dynamic programming.

This tutorial provides an in-depth exploration of Kadane’s Algorithm in C: problem understanding, naive O(n²) approach, optimized O(n) Kadane’s algorithm, tracking the actual subarray, practical implementation, common pitfalls, and best practices.

Conceptual Introduction & Fundamentals

What is the Maximum Subarray Sum?

Given an integer array arr[], find the contiguous subarray with the largest sum.

Examples:

text

Input: [2, 3, -8, 7, -1, 2, 3] Output: 11 Explanation: Subarray [7, -1, 2, 3] has sum 11. Input: [-2, -4] Output: -2 Explanation: Subarray [-2] has the maximum sum. Input: [5, 4, 1, 7, 8] Output: 25 Explanation: The entire array has the maximum sum.

Why This Problem Matters

• Dynamic programming foundation: Classic DP problem.
• Algorithm optimization: O(n²) → O(n) transformation.
• Interview preparation: Very common coding interview question.
• Real-world applications: Stock analysis, signal processing, bioinformatics.
• Foundation for variants: Maximum product subarray, circular subarray.

Key Insight

For each position, we decide:

• Extend the previous subarray if its sum is beneficial (positive contribution).
• Start fresh from the current element if the previous sum is negative.

Recurrence:

text

maxEnding[i] = max(maxEnding[i-1] + arr[i], arr[i]) result = max(result, maxEnding[i])

Approaches Overview

Syntax & Core Mechanics

Approach 1: Naive — Iterate Over All Subarrays

Use two nested loops to compute sums of all subarrays.

c

#include <stdio.h> #include <limits.h> int maxSubarraySumNaive(const int arr[], int n) { if (n <= 0) return 0; int maxSum = arr[0]; for (int i = 0; i < n; i++) { int currSum = 0; for (int j = i; j < n; j++) { currSum += arr[j]; if (currSum > maxSum) { maxSum = currSum; } } } return maxSum; } int main(void) { int arr[] = {2, 3, -8, 7, -1, 2, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("Maximum subarray sum: %d\n", maxSubarraySumNaive(arr, n)); return 0; }

Expected output:

text

Maximum subarray sum: 11

Time: O(n²), Space: O(1)

Approach 2: Kadane’s Algorithm

Track the maximum sum ending at each position.

c

#include <stdio.h> #include <limits.h> int maxSubarraySumKadane(const int arr[], int n) { if (n <= 0) return 0; int maxEnding = arr[0]; int result = arr[0]; for (int i = 1; i < n; i++) { /* Either extend previous subarray or start fresh */ if (maxEnding + arr[i] > arr[i]) { maxEnding = maxEnding + arr[i]; } else { maxEnding = arr[i]; } /* Update result */ if (maxEnding > result) { result = maxEnding; } } return result; } int main(void) { int arr[] = {2, 3, -8, 7, -1, 2, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("Maximum subarray sum: %d\n", maxSubarraySumKadane(arr, n)); return 0; }

Expected output:

text

Maximum subarray sum: 11

Time: O(n), Space: O(1)

Compact Kadane’s Formulation

c

int maxSubarraySum(const int arr[], int n) { int maxEnding = arr[0]; int result = arr[0]; for (int i = 1; i < n; i++) { maxEnding = (maxEnding + arr[i] > arr[i]) ? maxEnding + arr[i] : arr[i]; result = (result > maxEnding) ? result : maxEnding; } return result; }

Step-by-Step Trace for [2, 3, -8, 7, -1, 2, 3]

text

Init: maxEnding = 2, result = 2 i=1, x=3: maxEnding = max(2+3, 3) = 5; result = 5 i=2, x=-8: maxEnding = max(5-8, -8) = -3; result = 5 i=3, x=7: maxEnding = max(-3+7, 7) = 7; result = 7 i=4, x=-1: maxEnding = max(7-1, -1) = 6; result = 7 i=5, x=2: maxEnding = max(6+2, 2) = 8; result = 8 i=6, x=3: maxEnding = max(8+3, 3) = 11; result = 11 Final result = 11 (subarray [7, -1, 2, 3])

Tracking the Actual Subarray

To return the indices of the maximum subarray:

c

void maxSubarrayWithIndices(const int arr[], int n, int *maxSum, int *start, int *end) { int maxEnding = arr[0]; int currentStart = 0; int bestStart = 0; int bestEnd = 0; int result = arr[0]; for (int i = 1; i < n; i++) { if (maxEnding + arr[i] > arr[i]) { maxEnding = maxEnding + arr[i]; } else { maxEnding = arr[i]; currentStart = i; /* Start fresh from current */ } if (maxEnding > result) { result = maxEnding; bestStart = currentStart; bestEnd = i; } } *maxSum = result; *start = bestStart; *end = bestEnd; }

Full Practical Code Example with Explanation

This program demonstrates both approaches with verification, subarray tracking, performance comparison, and edge cases.

Program: Maximum Subarray Sum Finder

c

/** * max_subarray_sum.c * Finds maximum subarray sum using naive and Kadane's approaches. * Includes subarray tracking, verification, and edge cases. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <limits.h> #include <time.h> #define MAX_LINE_LEN 100 #define MAX_SIZE 100000 /* Function prototypes */ int maxSubarrayNaive(const int arr[], int n); int maxSubarrayKadane(const int arr[], int n); void maxSubarrayWithIndices(const int arr[], int n, int *maxSum, int *start, int *end); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); void printSubarray(const int arr[], int start, int end); void demonstrateApproaches(void); void performanceComparison(void); void demonstrateEdgeCases(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Maximum Subarray Sum (Kadane's Algorithm) ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate with Sample Arrays\n"); printf("2. Enter Custom Array\n"); printf("3. Performance Comparison\n"); printf("4. Edge Cases\n"); printf("5. Exit\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { fprintf(stderr, "Error reading choice.\n"); return EXIT_FAILURE; } choice = atoi(buffer); switch (choice) { case 1: demonstrateApproaches(); break; case 2: { int arr[MAX_SIZE]; int n; int maxSum, start, end; if (readInteger("Enter array size (1-100000): ", &n) != 0) { fprintf(stderr, "Invalid size.\n"); break; } if (n < 1 || n > MAX_SIZE) { printf("Size must be 1-%d.\n", MAX_SIZE); break; } printf("Enter %d elements:\n", n); for (int i = 0; i < n; i++) { char prompt[50]; snprintf(prompt, sizeof(prompt), " Element %d: ", i); if (readInteger(prompt, &arr[i]) != 0) { fprintf(stderr, "Invalid input.\n"); n = i; break; } } printf("\nArray: "); printArray(arr, n); int naive = maxSubarrayNaive(arr, n); int kadane = maxSubarrayKadane(arr, n); printf("Naive result: %d\n", naive); printf("Kadane result: %d\n", kadane); printf("Verification: %s\n", (naive == kadane) ? "PASS" : "FAIL"); maxSubarrayWithIndices(arr, n, &maxSum, &start, &end); printf("Maximum subarray: "); printSubarray(arr, start, end); break; } case 3: performanceComparison(); break; case 4: demonstrateEdgeCases(); break; case 5: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Naive: O(n^2) */ int maxSubarrayNaive(const int arr[], int n) { if (n <= 0) return 0; int maxSum = arr[0]; for (int i = 0; i < n; i++) { int currSum = 0; for (int j = i; j < n; j++) { currSum += arr[j]; if (currSum > maxSum) { maxSum = currSum; } } } return maxSum; } /* Kadane's: O(n) */ int maxSubarrayKadane(const int arr[], int n) { if (n <= 0) return 0; int maxEnding = arr[0]; int result = arr[0]; for (int i = 1; i < n; i++) { if (maxEnding + arr[i] > arr[i]) { maxEnding = maxEnding + arr[i]; } else { maxEnding = arr[i]; } if (maxEnding > result) { result = maxEnding; } } return result; } /* Kadane's with subarray indices */ void maxSubarrayWithIndices(const int arr[], int n, int *maxSum, int *start, int *end) { int maxEnding = arr[0]; int currentStart = 0; int bestStart = 0; int bestEnd = 0; int result = arr[0]; for (int i = 1; i < n; i++) { if (maxEnding + arr[i] > arr[i]) { maxEnding = maxEnding + arr[i]; } else { maxEnding = arr[i]; currentStart = i; } if (maxEnding > result) { result = maxEnding; bestStart = currentStart; bestEnd = i; } } *maxSum = result; *start = bestStart; *end = bestEnd; } /* Prints array */ void printArray(const int arr[], int n) { printf("["); for (int i = 0; i < n; i++) { printf("%d", arr[i]); if (i < n - 1) printf(", "); } printf("]\n"); } /* Prints subarray */ void printSubarray(const int arr[], int start, int end) { printf("["); for (int i = start; i <= end; i++) { printf("%d", arr[i]); if (i < end) printf(", "); } printf("]\n"); } /* Demonstrates both approaches */ void demonstrateApproaches(void) { printf("\n=== Sample Arrays ===\n"); int arr1[] = {2, 3, -8, 7, -1, 2, 3}; int n1 = sizeof(arr1) / sizeof(arr1[0]); printf("\nArray 1: "); printArray(arr1, n1); printf("Naive: %d\n", maxSubarrayNaive(arr1, n1)); printf("Kadane: %d\n", maxSubarrayKadane(arr1, n1)); int arr2[] = {-2, -4}; int n2 = sizeof(arr2) / sizeof(arr2[0]); printf("\nArray 2: "); printArray(arr2, n2); printf("Naive: %d\n", maxSubarrayNaive(arr2, n2)); printf("Kadane: %d\n", maxSubarrayKadane(arr2, n2)); int arr3[] = {5, 4, 1, 7, 8}; int n3 = sizeof(arr3) / sizeof(arr3[0]); printf("\nArray 3: "); printArray(arr3, n3); printf("Naive: %d\n", maxSubarrayNaive(arr3, n3)); printf("Kadane: %d\n", maxSubarrayKadane(arr3, n3)); int arr4[] = {-1, -2, -3, -4}; int n4 = sizeof(arr4) / sizeof(arr4[0]); printf("\nArray 4 (all negative): "); printArray(arr4, n4); printf("Kadane: %d\n", maxSubarrayKadane(arr4, n4)); /* Subarray tracking demonstration */ int maxSum, start, end; maxSubarrayWithIndices(arr1, n1, &maxSum, &start, &end); printf("\nArray 1 maximum subarray (sum = %d): ", maxSum); printSubarray(arr1, start, end); } /* Performance comparison */ void performanceComparison(void) { printf("\n=== Performance Comparison (n = 20000) ===\n"); int n = 20000; int *arr = malloc(n * sizeof(int)); if (arr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } srand(42); for (int i = 0; i < n; i++) { arr[i] = (rand() % 200) - 100; /* Range -100..99 */ } clock_t start, end; double timeTaken; start = clock(); int naiveResult = maxSubarrayNaive(arr, n); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Naive (O(n^2)): Result = %d, Time = %.3f ms\n", naiveResult, timeTaken); start = clock(); int kadaneResult = maxSubarrayKadane(arr, n); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Kadane (O(n)): Result = %d, Time = %.3f ms\n", kadaneResult, timeTaken); printf("\nVerification: %s\n", (naiveResult == kadaneResult) ? "PASS" : "FAIL"); free(arr); } /* Demonstrates edge cases */ void demonstrateEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Case 1: Single positive element */ int arr1[] = {42}; printf("Case 1: Single positive element\n"); printf(" Array: "); printArray(arr1, 1); printf(" Kadane: %d\n", maxSubarrayKadane(arr1, 1)); /* Case 2: Single negative element */ int arr2[] = {-5}; printf("\nCase 2: Single negative element\n"); printf(" Array: "); printArray(arr2, 1); printf(" Kadane: %d\n", maxSubarrayKadane(arr2, 1)); /* Case 3: All positive */ int arr3[] = {1, 2, 3, 4, 5}; printf("\nCase 3: All positive\n"); printf(" Array: "); printArray(arr3, 5); printf(" Kadane: %d (entire array)\n", maxSubarrayKadane(arr3, 5)); /* Case 4: All negative */ int arr4[] = {-3, -1, -4, -1, -5}; printf("\nCase 4: All negative\n"); printf(" Array: "); printArray(arr4, 5); printf(" Kadane: %d (single max element)\n", maxSubarrayKadane(arr4, 5)); /* Case 5: Alternating */ int arr5[] = {1, -2, 3, -4, 5, -6, 7}; printf("\nCase 5: Alternating\n"); printf(" Array: "); printArray(arr5, 7); printf(" Kadane: %d\n", maxSubarrayKadane(arr5, 7)); /* Case 6: Zeros included */ int arr6[] = {0, -1, 0, 2, 0}; printf("\nCase 6: Zeros included\n"); printf(" Array: "); printArray(arr6, 5); printf(" Kadane: %d\n", maxSubarrayKadane(arr6, 5)); /* Case 7: Large values (overflow check) */ int arr7[] = {1000000000, 1000000000, -1, 1000000000}; printf("\nCase 7: Large values\n"); printf(" Array: "); printArray(arr7, 4); printf(" Kadane: %d (watch for overflow)\n", maxSubarrayKadane(arr7, 4)); /* Case 8: Subarray tracking */ int arr8[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; int maxSum, start, end; maxSubarrayWithIndices(arr8, 9, &maxSum, &start, &end); printf("\nCase 8: Subarray tracking\n"); printf(" Array: "); printArray(arr8, 9); printf(" Max subarray: "); printSubarray(arr8, start, end); printf(" Sum: %d\n", maxSum); } /* Reads an integer safely */ int readInteger(const char *prompt, int *outValue) { char buffer[MAX_LINE_LEN]; char *endPtr; long val; printf("%s", prompt); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { return -1; } errno = 0; val = strtol(buffer, &endPtr, 10); if (endPtr == buffer || (*endPtr != '\n' && *endPtr != '\0')) { return -1; } if (errno == ERANGE || val < -2147483647 - 1 || val > 2147483647) { return -1; } *outValue = (int)val; return 0; }

Explanation of Approaches

1. Naive: Enumerates all subarrays; O(n²).
2. Kadane: Tracks maximum sum ending at each position; O(n).
3. Subarray Tracking: Extends Kadane’s to record start/end indices.
4. Overflow Protection: Uses int for typical cases; long long for large sums.

Expected Output (sample run)

text

=== Maximum Subarray Sum (Kadane's Algorithm) === --- Menu --- 1. Demonstrate with Sample Arrays 2. Enter Custom Array 3. Performance Comparison 4. Edge Cases 5. Exit Enter choice: 1 === Sample Arrays === Array 1: [2, 3, -8, 7, -1, 2, 3] Naive: 11 Kadane: 11 Array 2: [-2, -4] Naive: -2 Kadane: -2 Array 3: [5, 4, 1, 7, 8] Naive: 25 Kadane: 25 Array 4 (all negative): [-1, -2, -3, -4] Kadane: -1 Array 1 maximum subarray (sum = 11): [7, -1, 2, 3] --- Menu --- ... Enter choice: 3 === Performance Comparison (n = 20000) === Naive (O(n^2)): Result = 12345, Time = 234.567 ms Kadane (O(n)): Result = 12345, Time = 0.089 ms Verification: PASS --- Menu --- ... Enter choice: 4 === Edge Cases === Case 1: Single positive element Array: [42] Kadane: 42 Case 2: Single negative element Array: [-5] Kadane: -5 Case 3: All positive Array: [1, 2, 3, 4, 5] Kadane: 15 (entire array) Case 4: All negative Array: [-3, -1, -4, -1, -5] Kadane: -1 (single max element) Case 5: Alternating Array: [1, -2, 3, -4, 5, -6, 7] Kadane: 7 Case 6: Zeros included Array: [0, -1, 0, 2, 0] Kadane: 2 Case 7: Large values Array: [1000000000, 1000000000, -1, 1000000000] Kadane: 2000000000 (watch for overflow) Case 8: Subarray tracking Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4] Max subarray: [4, -1, 2, 1] Sum: 6

Common Pitfalls, Edge Cases & Memory Considerations

1. Empty Array

Return 0 or handle gracefully.

c

if (n <= 0) return 0;

2. All Negative Elements

Kadane’s algorithm correctly returns the maximum single element.

c

int arr[] = {-2, -4}; /* Result: -2 */

Important: Initialize maxEnding and result to arr[0], not 0.

3. Integer Overflow

For large values, the sum may exceed int.

c

long long maxEnding = arr[0]; /* Use long long for large sums */

Solution: Use long long for the result and intermediate sums.

4. Initialization Error

Initializing maxEnding = 0 breaks all-negative arrays.

c

int maxEnding = 0; /* BUG: returns 0 for all-negative arrays */ int maxEnding = arr[0]; /* Correct */

5. Off-by-One in Subarray Tracking

Record currentStart only when starting fresh.

c

if (maxEnding + arr[i] > arr[i]) { maxEnding += arr[i]; } else { maxEnding = arr[i]; currentStart = i; }

6. Confusing maxEnding and result

• maxEnding: maximum sum ending at current index.
• result: maximum sum found so far.

7. Using >= vs >

Using >= may change which subarray is returned when ties exist.

c

if (maxEnding > result) { /* Strict: keeps first occurrence */ result = maxEnding; }

8. Modifying the Input

Kadane’s algorithm does not modify the input.

9. Non-Contiguous Subarrays

Kadane’s only works for contiguous subarrays. For non-contiguous, sum all positive elements.

10. Memory Considerations

• Both approaches use O(1) extra space.
• No dynamic allocation required.
• Use long long for very large arrays.
• Subarray tracking adds constant space.

Summary & Best Practices

Kadane’s Algorithm is the optimal solution for the maximum subarray sum problem, achieving O(n) time and O(1) space. The key insight is deciding at each element whether to extend the previous subarray or start fresh.

Key Takeaways

• Maximum subarray sum: contiguous subarray with largest sum.
• Naive: O(n²) time, O(1) space.
• Kadane: O(n) time, O(1) space.
• Initialize with arr[0], not 0.
• Recurrence: maxEnding = max(maxEnding + arr[i], arr[i]).
• Works correctly with all-negative arrays.

Best Practices

1. Use Kadane’s Algorithm for O(n) time and O(1) space.
2. Initialize to arr[0] to handle all-negative arrays.
3. Use long long for large arrays to prevent overflow.
4. Track start/end indices when the actual subarray is needed.
5. Handle edge cases: empty, single element, all-negative.
6. Verify with naive approach during testing.
7. Document the recurrence in comments.
8. Test with zeros and alternating signs.
9. Use > (not >=) to keep the first occurrence.
10. Profile for large arrays.

By mastering Kadane’s Algorithm, you’ll have a powerful tool for solving dynamic programming and array problems.