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

dilip.mathews
3
Junior Poster in Training

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

Jump to PostThe maximum would be 5 + 10, just toss out all negative values.

Jump to PostFirst generate all the subsets, then add the totals.

The one with the biggest total wins?

Jump to PostThen 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 …

Jump to Postiamthwee,

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?

Jump to PostNo 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] = …

Ancient Dragon
5,243
Achieved Level 70
Team Colleague
Featured Poster

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

dilip.mathews
3
Junior Poster in Training

{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
978
Super Senior Demiposter
Team Colleague

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
3
Junior Poster in Training

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
3
Junior Poster in Training

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
3
Junior Poster in Training

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
978
Super Senior Demiposter
Team Colleague

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
3
Junior Poster in Training

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
0
Light Poster

Atanas
-1
Newbie Poster

Can somene publicate a code for this solution

Thanks

Salem
commented:
No, try your own homework first
-1

Ancient Dragon
5,243
Achieved Level 70
Team Colleague
Featured Poster

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
1,152
Posting Virtuoso

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
25
Newbie Poster

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
381
Search and Destroy

omko
25
Newbie Poster

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 ?

Ancient Dragon
commented:
great explaination :)
+25

hammerhead
19
Posting Whiz in Training

{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
25
Newbie Poster

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
381
Search and Destroy

How about this array [2, 4, 1, 5, 6]

so the maximun of subset sum is 2 + 4 + 1 + 5 + 6 = 17?

omko
25
Newbie Poster

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.