Maximum Subarray Problem - Iterative O(n) algorithm

Question

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;
}

Answer 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., &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;
}