Kadane maximum subarray

Question

Find the maximum sum of subarray with Kadane's algorithm

//test case 
int maxKanade, startKanade, endKanade;
maxKanade = Kadane(new List<int>() { 2, -4, 6, -3, 9 }, out startKanade, out endKanade);
Debug.WriteLine("{0} {1} {2}", maxKanade, startKanade, endKanade);
maxKanade = Kadane(new List<int>() { 3, 4, 6, -3, -9 }, out startKanade, out endKanade);
Debug.WriteLine("{0} {1} {2}", maxKanade, startKanade, endKanade);
//test case end

public static int Kadane(List<int> input, out int start, out int end)
{
    //from wiki https://en.wikipedia.org/wiki/Maximum_subarray_problem
    //def max_subarray(A):
    //max_ending_here = max_so_far = 0
    //for x in A:
    //    max_ending_here = max(0, max_ending_here + x)
    //    max_so_far = max(max_so_far, max_ending_here)
    //return max_so_far
    start = 0;
    int s = 0;
    end = 0;
    int count = 0;
    int max_ending_here = 0, max_so_far = 0;
    foreach(int i in input)
    {
        if (max_ending_here + i > 0)
        {
            max_ending_here += i;
        }
        else
        {
            // if go negative basically take a fresh start
            max_ending_here = 0;
            s = count + 1;
        }
        if (max_so_far < max_ending_here)
        {
            max_so_far = max_ending_here;
            end = count;
            start = s;
        }
        count++;
    }
    return max_so_far;
}

@200_success Sorry I had a misspell I semi fixed after the copy. I will fix. — paparazzo
– paparazzo, Commented Feb 23, 2017 at 4:38
Sorry I had a misspell - had? int maxKanade, startKanade, endKanade; and uses thereof. (Then, misspell is no noun in my book.) — greybeard
– greybeard, Commented Aug 18, 2017 at 5:28

alecxe · Accepted Answer · 2017-08-18 05:17:47Z

1

You could simplify that

if (max_ending_here + i > 0)
{
    max_ending_here += i;
}
else
{
    // if go negative basically take a fresh start
    max_ending_here = 0;
    s = count + 1;
}

with

max_ending_here += i;
if (max_ending_here <= 0)
{
    // if go negative basically take a fresh start
    max_ending_here = 0;
    s = count + 1;
}

edited Aug 18, 2017 at 5:17

alecxe

17.5k8 gold badges52 silver badges93 bronze badges

answered Feb 23, 2017 at 11:14

JanDotNet

8,6082 gold badges22 silver badges48 bronze badges

\$\begingroup\$ I ended up with something different but this got me going in that direction. \$\endgroup\$

paparazzo
– paparazzo

2017-02-25 17:06:59 +00:00
Commented Feb 25, 2017 at 17:06

Add a comment |

AlanT · Accepted Answer · 2017-02-23 10:04:34Z

Testing
When @200_success asked if you had tested the code you seemed puzzled and pointed out that you had included two tests. Unfortunately, writing things out to the screen and sight checking the results would not be considered good unit testing and for a reviewer they are not very useful as all we can tell is that some output was displayed. There is nothing to indicate what the expected results were or if they were achieved.

Also, two unit tests which pass is a limited subset to say that it is working.

What happens with an empty input?
What happens if they are all negative?
What happens if we have two sub-arrays which both have the same maximum value?

to a degree this is a gap in the requirements, the original Kadane only cares about the max value not the start and end.

Should we return start = 0 and end = 0 if there are no elements in the input or if all are negative. The result (0) is correct but it seems to indicate an array of length starting at 0, ending at 0.

Bottom line: Testing a function like this is a great place to use an automated unit testing framework. It may seem like doubling the code to be written but by the time one has run the code, read and checked the answers and repeated umpteen times for each tweak to the code to deal with the next thing we hadn't thought of, it does save time and gives a nice warm fuzzy feeling that we can see that it works and if any changes break it.

API
We do not use the List functionality anywhere in the function but insist that the user passes in a List. I would push for changing the interface to IEnumerable<int>.

It's a variation on an established algorithm - the original is a lot simpler because it doesn't care about start or end positions. The point of the comment is that sight checking Debug.WriteLine() statements as a mechanism for testing doesn't scale well. — AlanT
– AlanT, Commented Feb 23, 2017 at 10:56

Svek · Accepted Answer · 2017-02-24 07:10:22Z

2

A small contribution. This code block looks a bit unpleasant:

start = 0;
int s = 0;
end = 0;
int count = 0;
int max_ending_here = 0, max_so_far = 0;

You have two declaration styles, I would say that mixing them up isn't "fashionable" -- I guess is the word?

You could go with something like:

start = 0;
end = 0;
int s, count, max_ending_here, max_so_far = 0;

or

start = 0;
end = 0;
int s = 0;
int count = 0;
int max_ending_here = 0;
int max_so_far = 0;

answered Feb 24, 2017 at 7:10

Svek

1,0237 silver badges18 bronze badges

Add a comment |

paparazzo · Accepted Answer · 2017-02-23 14:53:58Z

1

Can move the check on max_so_far to inside the max_ending_here += i;
No reason to process 0

foreach(int i in input)
{
    if (i == 0)
    { }
    else if (max_ending_here + i > 0)
    {
        max_ending_here += i;
        if (max_so_far < max_ending_here)
        {
            max_so_far = max_ending_here;
            end = count;
            start = s;
        }
    }
    else
    {
        // if go negative basically take a fresh start
        max_ending_here = 0;
        s = count + 1;
    }       
    count++;
}

edited Feb 23, 2017 at 14:53

answered Feb 23, 2017 at 13:43

paparazzo

6,1363 gold badges20 silver badges43 bronze badges

Add a comment |

Stack Exchange Network

Kadane maximum subarray

4 Answers 4

You must log in to answer this question.

Hot Network Questions

Kadane maximum subarray

4 Answers 4

You must log in to answer this question.

Related

Hot Network Questions