Linear time algorithm for Maximum contiguous sub-array sum

Question

I have been solving exercise from Introduction to Algorithms - CLRS and came across solving maximum contiguous sub-array in linear time (Q 4.1-5). Please look at my solution below. I have been searching for online judges for this exercise but found none. After solving it when I looked for solutions I found kadane's algorithm which seems different than my implementation also this solution gives the correct output when all numbers are negative.

public static int linearMaxSolve(int[] arr) {
int max = Integer.MIN_VALUE;
int sum = 0;
for (int i : arr) {
    sum += i;
    if (i > sum) {
        sum = i;
    }
    if (sum > max) {
        max = sum;
    }
}
return max;
}

Is there a way to check the validity of this algorithm apart from feeding in manual test cases to the program?

Note that "Stack Overflow is not a discussion forum". (from the tour page) So, ask a question please. — user202729
– user202729, Commented Mar 11, 2018 at 6:56
One can argue what the correct output is if all array elements are negative. One possible answer is 0 (for the empty sub-array). — Henry
– Henry, Commented Mar 11, 2018 at 7:28

A. Sarid · Accepted Answer · 2018-03-11 08:47:38Z

5

This really depends on what is your definition for an array with all negative values.

In case you don't count the empty sub-array as a possible solution then yes, your solution is correct and actually it's exactly the same as the Kadane's algorithm.

int max_so_far = a[0];
int max_ending_here = a[0];

for (int i = 1; i < size; i++)
{
    max_ending_here = Math.max(a[i], max_ending_here+a[i]);
    max_so_far = Math.max(max_so_far, max_ending_here);
}
return max_so_far;

The only difference is the initialization, but if you'll take a closer look, at the first iteration of your algorithm, both sum and max will have the value of a[0].

But again, you assume here that both your array isn't empty (in that case you'll return Integer.MIN_VALUE, is that what you want?) and that an empty sub-array (sum==0) is not a possible solution.

answered Mar 11, 2018 at 8:47

A. Sarid

4,0042 gold badges34 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Linear time algorithm for Maximum contiguous sub-array sum

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related