4
\$\begingroup\$

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;
}
\$\endgroup\$
0

1 Answer 1

3
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.