Find Largest Sum Contiguous Subarray

Understanding the Problem

The goal is to find the subarray with the maximum sum in a given array using different methods.

Method 1: Kadane's Algorithm

This method efficiently finds the largest sum contiguous subarray using dynamic programming.

#include <stdio.h>
int maxSubArraySum(int arr[], int size) {
    int max_so_far = arr[0], max_ending_here = arr[0];
    for (int i = 1; i < size; i++) {
        max_ending_here = (arr[i] > max_ending_here + arr[i]) ? arr[i] : max_ending_here + arr[i];
        if (max_ending_here > max_so_far)
            max_so_far = max_ending_here;
    }
    return max_so_far;
}
int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int size = sizeof(arr)/sizeof(arr[0]);
    printf("Maximum contiguous sum: %d", maxSubArraySum(arr, size));
    return 0;
}
            

Output:

Maximum contiguous sum: 6

Method 2: Divide and Conquer

This method finds the largest sum subarray by dividing the array into halves recursively.

#include <stdio.h>
int maxCrossingSum(int arr[], int l, int m, int h) {
    int sum = 0, left_sum = -10000, right_sum = -10000;
    for (int i = m; i >= l; i--) {
        sum += arr[i];
        if (sum > left_sum) left_sum = sum;
    }
    sum = 0;
    for (int i = m+1; i <= h; i++) {
        sum += arr[i];
        if (sum > right_sum) right_sum = sum;
    }
    return (left_sum + right_sum > left_sum && left_sum + right_sum > right_sum) ? left_sum + right_sum : (left_sum > right_sum ? left_sum : right_sum);
}
int maxSubArraySum(int arr[], int l, int h) {
    if (l == h) return arr[l];
    int m = (l + h) / 2;
    int left = maxSubArraySum(arr, l, m);
    int right = maxSubArraySum(arr, m+1, h);
    int cross = maxCrossingSum(arr, l, m, h);
    return (left > right && left > cross) ? left : (right > cross ? right : cross);
}
int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int size = sizeof(arr)/sizeof(arr[0]);
    printf("Maximum contiguous sum: %d", maxSubArraySum(arr, 0, size-1));
    return 0;
}
            

Output:

Maximum contiguous sum: 6

Method 3: Brute Force

This method checks all subarrays and computes their sums to find the maximum sum.

#include <stdio.h>
int maxSubArraySum(int arr[], int size) {
    int max_sum = arr[0];
    for (int i = 0; i < size; i++) {
        int current_sum = 0;
        for (int j = i; j < size; j++) {
            current_sum += arr[j];
            if (current_sum > max_sum) max_sum = current_sum;
        }
    }
    return max_sum;
}
int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int size = sizeof(arr)/sizeof(arr[0]);
    printf("Maximum contiguous sum: %d", maxSubArraySum(arr, size));
    return 0;
}
            

Output:

Maximum contiguous sum: 6