This week's giveaway is in the Spring forum. We're giving away four copies of REST with Spring (video course) and have Eugen Paraschiv on-line! See this thread for details.

1) Get a pencil, some paper, and most importantly, a large eraser
2) Write down on the paper how YOU would solve the problem if you had to do it by hand.
3) revise it until it is crystal clear to anyone who reads it what the steps should be.

Don't even THINK about writing Java code until you have completed the above steps.

To be more specific, how do you KNOW that 2,5 is the largest possible sum of contiguous number? I don't believe it is. Prove it to me.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

1. If all numbers in your list are positive, then larger sum will have the whole list;

2. If all numbers in your list are negative, then larger sum will be maximum element in the list;

3. If there are as positive as negative numbers in the list. Denote positive numbers as P, and negative numbers as N. Then our list will look like that (in terms of java regular expressions): [PN]{n}, where 'n' is length of the list (list 1,2,3 = PPP; list 1,5,-10,2,5 = PPNPP). This notation shows, that the whole list is divided into groups of interchanging positive and negative numbers. Note that largest sum could be as single positive group, as sequence of positive-negative-positive groups. For example list 8,9,-2,3 (PPNP) - largest sum has the whole list.

Let's 'roll up' our list by writing in the new list sums of numbers in positive and negative groups. For list 1,5,-10,2,5 it will be 6,-10,7 (PPNPP -> PNP). Note, that as we are searching for largest contiguous sum, we may not consider (i.e. just eliminate from list) negative numbers in the beginning and in the end of the list, if any, because adding them to the whole sum could only decrease it. So for list -1,2,3,-4,-5,1,4,-9 new list will be 5,-9,5. New list always starts with positive number and ends with positive number. Let's write new list like this: PN PN ... PN P. Sum every PN pair and write this sum and last P number to the new list. Continue 'rolling up' the list until you have single positive number. This number will be your larges sum. And if you now 'unroll' this number back to the list, you will have your contiguous set with largest sum.

Examples:
1. [1,5],[-10],[2,5];
Roll up (PPNPP -> PNP): [6, -10], 7; (PN P list)
Roll up: -4, 7. Remove -4 from the beginning of the list, recieving single number 7 - our desired sum. Unrolling: 7 is 2 + 5 => our largest set is [2,5]

2. [8,9],[-2],[3];
Roll up (PPNP -> PNP): [17, -2], [3];
Roll up: 15, 3;
Roll up: 18; So sum is 18, unrolling it back: 18 = 15 + 3 = (17 - 2) + 3 = ((8 + 9) - 2) + 3 => our largest sum is the whole list.

3. [3],[-2,-5],[2],[-10],[10,7],[-4,-3],[6,5],[-8],[9];
Roll up (PNNPNPPNNPPNP -> PNPNPNPNP): [3,-7],[2,-10],[17,-7],[11,-8],[9];
Roll up: -4,-8,10,3,9; Removing negative numbers from the beginning of the list - 10,3,9
Roll up: 22 is our desired sum; Unrolling: 22 = 10 + 3 + 9 = (17 - 7) + (11 - 8) + 9 = ((10 + 7) - ((-4) + (-3))) + ((6 + 5) - 8) + 9; largest set is 10,7,-4,-3,6,5,-8,9

4. 8,-5,4,3,4,-5,-5,4,6,-3;
Roll up: 8,-5,11,-10,10,-3. Removing -3 from the end of the list and rolling up again.
Roll up: 3,1,10. Our desired sum is 14, unrolling: 14 = 3 + 1 + 10 = (8 - 5) + (11 - 10) + 10 = (8 - 5) + ((4 + 3 + 4) - ((-5) + (-5))) + (4 + 6); largest set is 8,-5,4,3,4,-5,-5,4,6;

Pankaj Kumarkk
Ranch Hand

Joined: Apr 17, 2011
Posts: 110

posted

0

Hi Andrey Kozhanov,
Thanks for the great algorithm. Really interesting and creative way to approach the problem. I would also like to learn "how to create a algorithm" for problems. Would you suggest any book or resources which will help me get better at tacking problems and coming up with good algorithms.
These days I am going to through "Introduction to Algorithms 2nd ed - T. Cormen, C. Leiserson, R. Rivest, C. Stein" for same.
Is there any other thing you would suggest.

Thanks,
Satish

Andrey Kozhanov
Ranch Hand

Joined: Mar 12, 2010
Posts: 79

posted

0

Satish Kumarkk wrote:Would you suggest any book or resources which will help me get better at tacking problems and coming up with good algorithms

Well, the only book devoted to algorithms i know is 'The art of computer programming' by Donald Knuth. And when i could not find any suitable algorithm i just create my own using logic and common sence.