Max Subarray

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <limits.h>


/* Utitlites. TO BE IGNORED. */
/* ======================================================================== */
#define NEWLINE puts("");
#define dd printf("HERE %d\n", __LINE__); // Used for debugging.

#define NELEMS(x) (sizeof(x)/sizeof(x[0]))
#define max(x,y) (((x) > (y)) ? (x) : (y))
#define min(x,y) (((x) > (y)) ? (y) : (x))

/* For itr = [start, end]; */
#define forIn(itr, start, end) \
    for (unsigned int itr = (start); (itr) < (end); ++(itr))

#define assert(expr, err_msg, err_expr)         \
    if (!(expr)) {                              \
        printf(err_msg);                        \
        err_expr;                               \
    }

/* Array concatenation. */
#define arrcat(t, t_nelems, s, s_nelems) {      \
    forIn(s_index, 0, s_nelems) {               \
            t[t_nelems + s_index] = s[s_index]; \
    } }

/* Error codes. */
enum errcode {
    SUCCESS,
    ERROR,
    NULL_INPUT = -'I',
    DOMAIN_ERR,  // Input does not belong to the domanin of the function.
    NOT_FOUND = 404,
    FOUND = -404,
    NIL = '0',
    RESOURCE_ACQUISITION_FAILED = 7
};
typedef enum errcode errcode;


/* Error checked malloc, realloc and calloc. */
void *ec_malloc(size_t);
void *ec_realloc(void *, size_t);
void *ec_calloc(size_t, size_t);

/* Allocate memory for an array of the given type. */
#define mem_arr(type, ptr, size) \
    (ptr) = (type *) ec_malloc((size) * sizeof(type))
#define mem_arr_calloc(type, ptr, size) \
    (ptr) = (type *) ec_calloc(size, sizeof(type));

/* Allocate a matrix of any type. */
#define mem_matrix(type, matrix, rows, cols)    \
    mem_arr(type*, matrix, rows);               \
    forIn (i, 0, rows) {                        \
        mem_arr(type, matrix[i], cols);         \
    }
#define mem_matrix_calloc(type, matrix, rows, cols)     \
    mem_arr_calloc(type*, matrix, rows);                \
    forIn (i, 0, rows) {                                \
        mem_arr_calloc(type, matrix[i], cols);          \
    }

/* Deallocate a matrix of any type. */
#define free_matrix(matrix, rows)               \
    forIn (i, 0, rows) {                        \
        free(matrix[i]);                        \
    }                                           \
    free(matrix);

/* Variable length TAB. */
#define TAB(length) printf("%" #length "c", 0)

/* Strtol wrapper. */
#define strtol_(str, identifier, calling_fn, err_expr) {                        \
    identifier = strtol(str, &err, 10);                                         \
    if (*err) {                                                                 \
            printf("[Error] " #calling_fn ": \"%s\" is not a number.\n", str);  \
            err_expr;                                                           \
    } }

typedef struct {
    char *s;
    unsigned int len;
} String;

/* Return a token from a given file descriptor. */
String ftok(FILE *fd, const char *del);

#define assert_ftok(fd, token, del, err_expr)   \
        assert((token = ftok(fd, del)).len, "", \
            free(token.s); err_expr);

/* Erorr checked fopen(). */
FILE *ec_fopen(const char *file_path, const char *mode);

/* Assert if file at =file_path= is empty. */
#define file_isEmpty(file_path, eof_expr) do {                                              \
    FILE *fd_test = ec_fopen(file_path, "a+");                                              \
    assert(fgetc(fd_test) != EOF && !feof(fd_test), "",                                     \
               printf("File %s is empty.\n", file_path); fclose(fd_test); eof_expr; break); \
    fclose(fd_test);                                                                        \
    } while(0)

/* Read array. */
#define freadarr(fd, format_specifier, arr, nelems)  do {       \
        forIn (i, 0, nelems) {                                  \
            if (EOF == fscanf(fd, format_specifier, arr + i)) { \
                nelems = i; break;                              \
            }                                                   \
        }                                                       \
    } while(0)
/* Print array. */
#define fprintarr(fd, format_specifier, arr, nelems)    \
    forIn (i, 0, nelems) {                              \
        fprintf(fd, format_specifier, *(arr + i));      \
    }                                                   \
    NEWLINE;                                            \

/* Read matrix. */
#define freadmat(fd, format_specifier, matrix, rows,  cols)  do {                           \
    int err = 0;                                                                            \
        forIn (ln_index, 0, rows) {                                                         \
            forIn (col_index, 0, cols) {                                                    \
                if ( EOF == fscanf(fd, format_specifier,matrix[ln_index] + col_index)) {    \
                    if ((!col_index && !ln_index) || col_index) cols = col_index;           \
                    err = 1;                                                                \
                }                                                                           \
            }                                                                               \
            if (err) { rows = ln_index; break; }                                            \
        }                                                                                   \
    } while(0)
/* Print matrix. */
#define fprintmat(fd, format_specifier, matrix, rows,  cols)                \
    NEWLINE;                                                                \
    forIn (ln_index, 0, rows) {                                             \
        forIn (col_index, 0, cols) {                                        \
            fprintf(fd, format_specifier " ",matrix[ln_index][col_index]);  \
        }                                                                   \
        NEWLINE;                                                            \
    }                                                                       \
    NEWLINE;
/* ======================================================================== */


/* BEGIN */

typedef struct Subarray_Sum {
    int sum;
    unsigned int left_i, right_i;
} Subarray_Sum;

Subarray_Sum find_max_crossing_subarray(int arr[], int lo, int mid, int hi);
Subarray_Sum find_max_subarray(int arr[], int lo, int hi);

#define INPUT_FILE "input.txt"

int main(int argc, char **argv)
{
    int arr[100];
    unsigned int nelems = 100;

    file_isEmpty(INPUT_FILE, return -1);

    FILE *input = ec_fopen(INPUT_FILE, "r");
    freadarr(input, "%d", arr, nelems);

    Subarray_Sum max_subarray = find_max_subarray(arr, 0, nelems - 1);

    fprintarr(stdout, "%d ",
        arr + max_subarray.left_i,
        max_subarray.right_i - max_subarray.left_i + 1);

    printf("%d\n", max_subarray.sum);

    return 0;
}

Subarray_Sum find_max_subarray(int arr[], int lo, int hi)
{
    if (hi == lo) {
        return (Subarray_Sum) { arr[hi], lo, hi };
    }

    Subarray_Sum left_sub, right_sub, crossing_sub;
    int mid;

    mid = (lo + hi) / 2;

    left_sub = find_max_subarray(arr, lo, mid);
    right_sub = find_max_subarray(arr, mid + 1, hi);
    crossing_sub = find_max_crossing_subarray(arr, lo, mid, hi);

    if (left_sub.sum >= right_sub.sum && left_sub.sum >= crossing_sub.sum) {
        return left_sub;
    }
    if (right_sub.sum >= left_sub.sum && right_sub.sum >= crossing_sub.sum) {
        return right_sub;
    }
    return crossing_sub;
}

Subarray_Sum find_max_crossing_subarray(int arr[], int lo, int mid, int hi)
{
    int left_i, right_i, sum = 0, left_sum = INT_MIN, right_sum = INT_MIN;

    for (int i = mid; i >= lo; --i) {
        sum += arr[i];
        if (sum > left_sum) {
            left_sum = sum;
            left_i = i;
        }
    }

    sum = 0;
    for (int i = mid + 1; i <= hi; ++i) {
        sum += arr[i];
        if (sum > right_sum) {
            right_sum = sum;
            right_i = i;
        }
    }

    return (Subarray_Sum) { right_sum + left_sum, left_i, right_i };
}

/* END */





/* Utilites. TO BE IGNORED. */
/* ======================================================================== */
/* Return a token from a given file descriptor. */
String ftok(FILE *fd, const char *del)
{
    String token;
    unsigned int size = 30, s_index = 0;
    char c;

    mem_arr(char, token.s, size);

    /* Ignore initial delimiters. */
    while ((c = fgetc(fd)) != EOF && strchr(del, c)) { ; }

    if (c == EOF) {
        free(token.s);
        return (String) { NULL, 0 };
    }

    do {
        if (s_index >= size) {
            token.s = (char *)ec_realloc(token.s, size += 30);
        }
        *(token.s + s_index) = c;
        ++s_index;
    } while ((c = fgetc(fd)) != EOF && !strchr(del, c));

    token.s = (char *)ec_realloc(token.s, s_index + 1); // "Tight fitting" string.
    token.s[s_index] = 0; // End string.
    token.len = s_index;

    return token;
}

/* I/O handling. */
FILE *ec_fopen(const char *file_path, const char *mode)
{
    FILE *fd;

    fd = fopen(file_path, mode);

    if (NULL == fd) {
        puts("[Error] fopen() returned NULL.");
        exit(RESOURCE_ACQUISITION_FAILED);
    }

    return fd;
}

/* Memory management. */
#define assert_alloc(allocator_name)                            \
    assert((new_ptr != NULL),                                   \
           "[Error] " #allocator_name "() returned NULL.\n",    \
           exit(RESOURCE_ACQUISITION_FAILED));
void *ec_calloc(size_t nitems, size_t size)
{
    void *new_ptr;

    new_ptr = calloc(nitems, size);
    assert_alloc(calloc);

    return new_ptr;
}
void *ec_realloc(void *ptr, size_t size)
{
    void *new_ptr;

    new_ptr = realloc(ptr, size);
    assert_alloc(realloc);

    return new_ptr;
}
void *ec_malloc(size_t size)
{
    return ec_realloc(NULL, size);
}
/* ======================================================================== */