Pankaj Kumarkk

Ranch Hand

Posts: 112

posted 6 years ago

Hi,

I am trying to solve a problem and am not able to find out how to approach this. If anybody can give any pointers then it will be helpful.

Problem:

You have a list of n numbers and from this list find combination of a contiguous set which has largest sum

e.g

list 1,2,3

answer: 1,2,3 (as sum of 1,2,3 is 6 which is largest possible for a set of contiguous numbers)

list 1,5,-10,2,5

answer: 2,5 (as 7 is largest sum possible for a set of contiguous numbers)

I am trying to solve a problem and am not able to find out how to approach this. If anybody can give any pointers then it will be helpful.

Problem:

You have a list of n numbers and from this list find combination of a contiguous set which has largest sum

e.g

list 1,2,3

answer: 1,2,3 (as sum of 1,2,3 is 6 which is largest possible for a set of contiguous numbers)

list 1,5,-10,2,5

answer: 2,5 (as 7 is largest sum possible for a set of contiguous numbers)

posted 6 years ago

to paraphrase my friend Campbell...

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.

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

Andrey Kozhanov

Ranch Hand

Posts: 79

posted 6 years ago

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

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;

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

Posts: 112

posted 6 years ago

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

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

Posts: 79

posted 6 years ago

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.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