To find the maximum subset sum in an array.

[dilip.mathews]

Hi all,

Can anybody help me with a an algorithm to find the maximum subset sum in an array.
It would be better if the solution is of O(n).
[example: {5,-2,10,-4} the maximum is 5 + (-2) + 10 => 13].

[Ancient Dragon]

The maximum would be 5 + 10, just toss out all negative values.

[dilip.mathews]

I dont want the maximum sum . I want the subset with maximum sum.
{5,-2,10,-4}
Here the subset with maximum sum is {5,-2,10,-4}. The program should output {5,-2,10}
I think u got my point.

[iamthwee]

First generate all the subsets, then add the totals.

The one with the biggest total wins?

[Rashakil Fol]

Then you mean the maximum sublist sum, not subset.

First, you can convert the list into a list of cumulative sums, turning [5,-2,10,-4] into [0,5,3,13,9]. Then walk through the list of cumulative sums, saving the smallest value so far and the maximum difference between what you see as the current value and what is currently the smallest value.

Of course, you don't have to actually create a list of cumulative sums; you can keep track of the cumulative sum as you walk through the first list.

[dilip.mathews]

Rashakil,

Seems like a good logic let me try to implement this.
But dont u think that then also I have to walk thru the array twice?

[dilip.mathews]

First generate all the subsets, then add the totals.

The one with the biggest total wins?

iamthwee,

I will go for this logic as a last option. I think the algo will be bulky as it will consume lots of space.

[iamthwee]

iamthwee,

I will go for this logic as a last option. I think the algo will be bulky as it will consume lots of space.

Well what are you doing? What is this algorithm for?

[dilip.mathews]

Well what are you doing? What is this algorithm for?

I have seen this ques in some website, I just wanted to know the efficient way to do it. I have some solution, but doesnt seems efficient.

[Rashakil Fol]

Rashakil,

Seems like a good logic let me try to implement this.
But dont u think that then also I have to walk thru the array twice?

Well, no, you don't; I've implemented this before. And even if you did, what's worng with walking through the array twice? It's still linear time.

[dilip.mathews]

Well, no, you don't; I've implemented this before. And even if you did, what's worng with walking through the array twice? It's still linear time.

Agreed its linear time. Let me try with one pass.
Anyway thanks for the help.

[joshilay]

i guess u can try some recursive algorithm for this .but with that 0(n) is still tough .. with recursive u can try maximum combinations while keeping efficiency ..

[Atanas]

Can somene publicate a code for this solution
Thanks

[Ancient Dragon]

Can somene publicate a code for this solution
Thanks

Nope -- its a secret :) Seriously, you should attempt to solve it yourself and then start your own thread to ask questions.

[vijayan121]

This problem is covered in detaill in Jon Bentley's Programming Pearls (Second Edition)
ISBN 81-7808-022-2 (Pearson Education)
see column 8 : Algorithm Design Techniques (pages 77-86)

Even if you have been programming for a number of years,
but have not seen this book so far, do yourself a favour. Get a copy.

[omko]

Hello
I'm thinking in a way, but I don't know if it can be implemented in O(n) way

first, we take the integral of the array
for example A = [1,2,3,4,5]
would give us the integral B = [1,2,6,10,15]

then we shall find the maximum difference between two items in this integral, such that the maximum index > minimum index

and these indexes ( indices ) are the first and end of the maximum subset

does that make sense ?

[invisal]

Sorry, but I still don't understand what is "subset with maximum sum". Can anyone explain or give me more examples?

[omko]

No problem, I also didn't get the idea when I heard about it

let's take for example this array ( [1,-2,3,-4])
what's the consecutive subsets ( subarrays ) which we can derive from it, and their sums

[1] = 1
[1,-2] = -1
[1,-2,3] = 2
[1,-2,3,-4] = 2-
[-2] = -2
[-2,3] = 1
..
[3] = 3
[3,-4] = -1

[-4]

so, the algorithm must return the subarray [3] which has the biggest sum which is 3

more examples ?

[hammerhead]

I dont want the maximum sum . I want the subset with maximum sum.
{5,-2,10,-4}
Here the subset with maximum sum is {5,-2,10,-4}. The program should output {5,-2,10}
I think u got my point.

I dont understand, sum of the subset [5,10] is clearly greater than that of [5,-2,10]

[omko]

I know , but in this question we want consecutive items, 5 and 10 are not, it's not a { } set
it's [ ], so we care about ordering

in my example , I can't get [1,-4] for example

got it ?

[invisal]

How about this array [2, 4, 1, 5, 6]
so the maximun of subset sum is 2 + 4 + 1 + 5 + 6 = 17?

[omko]

Ya , because an Input array with all items are positive is a special case, the algorithm must return the whole array

it's hard to work with an array with negative elements inside