Maximum Subarray Problem - Iterative O(n) algorithm
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;
}