# 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<stdio.h>

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, &low, &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(&max_sum, &max_low, &max_high);
initialize(&bet_sum, &bet_low, &bet_high);
initialize(&inc_sum, &inc_low, &inc_high);

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

} else {
update_var(array[i], &bet_sum, &bet_low, &bet_high, i);
if (inc_sum + array[i] > inc_sum) {
update_var(array[i], &inc_sum, &inc_low, &inc_high, i);
if (inc_sum > max_sum) {
max_sum = inc_sum;
max_low = inc_low;
max_high = inc_high;
initialize(&bet_sum, &bet_low, &bet_high);
initialize(&inc_sum, &inc_low, &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

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., &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->sum = 0;
sa->lower = sa->upper = i;
}

static void extend_subarray(subarray *sa, size_t i, int increase) {
sa->sum += increase;
sa->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(&max, *lower);
init_subarray(&tmp, *lower);

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

if (tmp.sum > 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, &lower, &upper));
printf("%zu %zu\n", lower, upper);

return 0;
}