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