Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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 auxillary 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;
}
share|improve this question

1 Answer

The explanation: here.

#include<stdio.h>

int max_sum_subsequence(int array[], int n)
{
    int maxSum = 0;
    int thisSum = 0;
    int i = 0;
    for(i = 0; i < n; i++)
    {
        thisSum += array[i];
        if (thisSum > maxSum) maxSum = thisSum;
        else
           if (thisSum < 0) thisSum = 0;
    }
    return maxSum;
}

int main(int argc, char* argv[])
{
    int array[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
    printf("max_sum_subsequence: %d\n", max_sum_subsequence(array, sizeof array / sizeof *array));      

}

PS. You can compare the speed of your solution here.

share|improve this answer
 
Care to explain how this works? –  Aseem Bansal Aug 30 at 15:04
 
Also doesn't the maximum subarray problem require the positions of the maximum subarray? –  Aseem Bansal Aug 30 at 15:07
 
There are could be few positions of a maximum subarray. –  cat_baxter Aug 30 at 15:09
 
Yeah there can be more than one positions of a maximum subarray. You missed finding at least one of them which is requirement for the maximum subarray problem. Wikipedia's code misses out of that also but the first sentence states that maximum subarray problem is the task of finding the contiguous subarray. If that is not done then the code just finds the sum which is incomplete solution. Also anything about my implementation? –  Aseem Bansal Aug 30 at 17:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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