Maximum Subarray Problem - Iterative O(n) algorithm I implemented an iterative \$O(n)\$ algorithm for solving the maximum sub-array problem. I would like a general review for it.

Here the max_subarray is the main function and the ones which are static are auxiliary functions for it.

#include&lt;stdio.h&gt;

int max_subarray(int array[], int *low, int *high);

static void initialize(int *sum, int *low, int *high);
static void update_var(int increase, int *sum, int *low, int *high, int i);

int main()
{
    //The maximum subarray-sum is 43 for the following
    int array[16] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
    int low = 0;
    int high = 15;

    printf("%d", max_subarray(array, &amp;low, &amp;high));
    printf("\n%d %d", low, high);

    return 0;
}

int max_subarray(int array[], int *low, int *high)
{
    int max_sum, max_low, max_high;
    int bet_sum, bet_low, bet_high;
    int inc_sum, inc_low, inc_high;

    initialize(&amp;max_sum, &amp;max_low, &amp;max_high);
    initialize(&amp;bet_sum, &amp;bet_low, &amp;bet_high);
    initialize(&amp;inc_sum, &amp;inc_low, &amp;inc_high);

    for (int i = *low; i &lt;= *high; i++)
    {
        if (max_sum + bet_sum + array[i] &gt; max_sum) {
            update_var(bet_sum + array[i], &amp;max_sum, &amp;max_low, &amp;max_high, i);
            initialize(&amp;bet_sum, &amp;bet_low, &amp;bet_high);
            initialize(&amp;inc_sum, &amp;inc_low, &amp;inc_high);

        } else {
            update_var(array[i], &amp;bet_sum, &amp;bet_low, &amp;bet_high, i);
            if (inc_sum + array[i] &gt; inc_sum) {
                update_var(array[i], &amp;inc_sum, &amp;inc_low, &amp;inc_high, i);
                if (inc_sum &gt; max_sum) {
                    max_sum = inc_sum;
                    max_low = inc_low;
                    max_high = inc_high;
                    initialize(&amp;bet_sum, &amp;bet_low, &amp;bet_high);
                    initialize(&amp;inc_sum, &amp;inc_low, &amp;inc_high);
                }
            }
        }
    }
    *low = max_low;
    *high = max_high;
    return max_sum;
}

static void update_var(int increase, int *sum, int *low, int *high, int i)
{
    *sum += increase;
    *high = i;
    if (*low == -1) {
        *low = i;
    }
}

static void initialize(int *sum, int *low, int *high)
{
    *sum = 0;
    *low = -1;
    *high = -1;
}
Subarray representation


Name of low and high: I prefer lower and upper because they contain the same number of characters, so that code lines up nicely. ☺︎
Inclusive-inclusive intervals: Your low and high variables form an inclusive-inclusive interval.  Usually, you would be better off with an inclusive-exclusive interval, especially in a language with zero-based arrays.  Consider examples


std::vector::end in C++
String.substring(beginIndex, endIndex) in Java
range(start, stop) in Python


The generic benefit of having high being one greater than the last element is that high - low is the number of elements.  This is nicer — you don't have to hard-code 16 or 15 anywhere:

int array[] = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };
int lower = 0, upper = sizeof(array) / sizeof(array[0]);


A specific benefit for this problem is that any interval with lower == upper represents an empty interval.  You don't have to use -1 for that.
Type of low and high: Array indices should be size_t rather than int.  Especially since your array consists of ints, there could be confusion as to whether int *lower should be a pointer to the first data element (i.e., &amp;array[0]) or a pointer to the index of the first element.  Not having to support -1 lets you use size_t instead, which clarifies your intentions.
Clusters of variables: Variables blah_sum, blah_low, and blah_high are always initialized and updated together.  There should be a struct representing subarrays, with operations "init" and "extend".

typedef struct {
    int sum;
    size_t lower;
    size_t upper;
} subarray;

static void init_subarray(subarray *sa, size_t i) {
    sa-&gt;sum = 0;
    sa-&gt;lower = sa-&gt;upper = i;
}

static void extend_subarray(subarray *sa, size_t i, int increase) {
    sa-&gt;sum += increase;
    sa-&gt;upper = i + 1;
}



Nitpicks


Const-correctness: max_subarray() should take a const int array[].
Brace style: Pick a brace style and stick with it.


Algorithm

Your code is wrong.  For an input array { -1, 5 }, it prints 4 instead of 5 as the maximum sum.

As @cat_baxter points out, Kadane's algorithm is simpler.

/**
 * Finds the earliest consecutive block of array elements with the maximum sum.
 *
 * Parameters:
 * lower  IN: a pointer to an integer that is the array index of the first
 *            element to consider (normally 0).
 *       OUT: a pointer to an integer that is the array index of the first
 *            element of the maximum subarray.
 *
 * upper  IN: a pointer to an integer that is one greater than the array index
 *            of the last element to consider (normally sizeof(array) /
 *            sizeof(int)).
 *       OUT: a pointer to an integer that is one greater than the array index
 *            of the last element of the maximum subarray.
 *
 * Returns: the sum of the maximum subarray
 */
int max_subarray(const int array[], size_t *lower, size_t *upper) {
    subarray max, tmp;
    init_subarray(&amp;max, *lower);
    init_subarray(&amp;tmp, *lower);

    for (int i = *lower; i &lt; *upper; i++) {
        if (tmp.sum &lt; 0) {
            init_subarray(&amp;tmp, i);
        }
        extend_subarray(&amp;tmp, i, array[i]);

        if (tmp.sum &gt; max.sum) {
            max = tmp;
        }
    }
    *lower = max.lower;
    *upper = max.upper;
    return max.sum;
}

int main() {
    //The maximum subarray-sum is 43 for the following
    int array[] = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };
    size_t lower = 0, upper = sizeof(array) / sizeof(array[0]);

    printf("%d\n", max_subarray(array, &amp;lower, &amp;upper));
    printf("%zu %zu\n", lower, upper);

    return 0;
}