Maximum subarray problem

max_subarray.c

#include <stdio.h>
#include <limits.h>
#include <math.h>

int find_max_cross_array(int A[], int low, int mid, int high,
    int *left, int *right) {
    
    int max_left, max_right;

    int sum = 0;
    int left_sum = INT_MIN;
    for (int i = mid; i >= low; i--) {
        sum += A[i];
        if (sum > left_sum) {
            max_left = i;
            left_sum = sum;
        }
    }

    sum = 0;
    int right_sum = INT_MIN;
    for (int i = mid+1; i <= high; i++) {
        sum += A[i];
        if (sum > right_sum) {
            max_right = i;
            right_sum = sum;
        }
    }

    *left = max_left;
    *right = max_right;
    return (left_sum + right_sum);
}


int find_max_array(int A[], int low, int high, int *left, int *right) {
    if (low == high) {
        *left = low; *right = high;
        return A[low];
    }
    else {
        int left_low, left_high, left_sum;
        int right_low, right_high, right_sum;
        int cross_low, cross_high, cross_sum;
        int mid = (int)floor((low + high) / 2.0);

        printf("%d %d %d\n", low, mid, high);

        left_sum = find_max_array(A, low, mid, &left_low, &left_high);
        right_sum = find_max_array(A, mid+1, high, &right_low, &right_high);
        cross_sum = find_max_cross_array(A, low, mid, high, &cross_low, &cross_high);

        if (left_sum >= right_sum && left_sum >= cross_sum) {
            *left = left_low; *right = left_high;
            return left_sum;
        }
        else if (right_sum >= left_sum && right_sum >= cross_sum) {
            *left = right_low; *right = right_high; 
            return right_sum;
        }
        else {
            *left = cross_low; *right = cross_high;
            return cross_sum;
        }
    }
}


int max_subarray_brute_force(int A[], int low, int high,
    int *left, int *right) {

    int sum = 0, max = INT_MIN;
    int right_idx = 0, left_idx = 0;
    for (int i = low; i <= high; i++) {
        sum = A[i];
        for (int j = i+1; j <= high; j++) {
            sum += A[j];
            if (sum > max) {
                max = sum;
                left_idx = i;
                right_idx = j;
            }
        }
    }

    *left = left_idx;
    *right = right_idx;
    return max;
}


int main(int argc, char **argv) {
    int left, right, sum;
    int A[16] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
    // int A[7] = {-3, -16, -23, -7, -5, -22, -4};
    // sum = find_max_array(A, 0, 15, &left, &right);
    // sum = find_max_array(A, 0, 5, &left, &right);
    sum = max_subarray_brute_force(A, 0, 15, &left, &right);

    printf("(%d, %d) : %d\n", left, right, sum);

    return 0;
}