 |  |  |  |  |  |  |  |
To find the maximum subset sum in an array.
 |
•
•
Join Date: Jun 2006
Posts: 89
Reputation: 
Solved Threads: 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].
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].
•
•
Join Date: Aug 2005
Posts: 15,381
Reputation: 
Solved Threads: 1466
The maximum would be 5 + 10, just toss out all negative values.
Last edited by Ancient Dragon; Jul 3rd, 2006 at 8:42 am.
•
•
Join Date: Jun 2006
Posts: 89
Reputation:
Solved Threads: 3
Junior Poster in Training
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.
{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.
•
•
Join Date: Aug 2005
Posts: 5,264
Reputation:
Solved Threads: 377
First generate all the subsets, then add the totals.
The one with the biggest total wins?
The one with the biggest total wins?
*Voted best profile in the world*
•
•
Join Date: Jun 2005
Posts: 2,039
Reputation:
Solved Threads: 139
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.
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.
All my posts may be redistributed under the GNU Free Documentation License.
•
•
Join Date: Jun 2006
Posts: 89
Reputation:
Solved Threads: 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?
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?
•
•
Join Date: Jun 2006
Posts: 89
Reputation:
Solved Threads: 3
Junior Poster in Training
•
•
•
•
Originally Posted by iamthwee
First generate all the subsets, then add the totals.
The one with the biggest total wins?
I will go for this logic as a last option. I think the algo will be bulky as it will consume lots of space.
•
•
Join Date: Aug 2005
Posts: 5,264
Reputation:
Solved Threads: 377
•
•
•
•
Originally Posted by dilip.mathews
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.
*Voted best profile in the world*
•
•
Join Date: Jun 2006
Posts: 89
Reputation:
Solved Threads: 3
Junior Poster in Training
•
•
•
•
Originally Posted by iamthwee
Well what are you doing? What is this algorithm for?
•
•
Join Date: Jun 2005
Posts: 2,039
Reputation:
Solved Threads: 139
•
•
•
•
Originally Posted by 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?
All my posts may be redistributed under the GNU Free Documentation License.
|
Other Threads in the C Forum
- Previous Thread: C Progamming
- Next Thread: Function Problems
| Thread Tools | Search this Thread |
You need to join our community in order to build your list of favorite forums. You can visit the forum index for a listing of all forums.
Related Forum Features
Latest C Posts
- Today's Posts
- Unanswered Threads
#include adobe ansi api array asterisks binarysearch changingto char character cm copyimagefile cprogramme creafecopyofanytypeoffileinc createcopyoffile csyntax database directory dynamic execv feet fgets file fork forloop frequency function getlasterror givemetehcodez global grade graphics gtkgcurlcompiling hacking hardware highest histogram i/o include incrementoperators infiniteloop input interest kernel keyboard kilometer license linked linkedlist linux linuxsegmentationfault list locate logical_drives looping loopinsideloop. lowest match matrix meter microsoft motherboard mqqueue mysql number odf opensource owf pattern pdf performance pointer posix probleminc process program programming radix recursion recv repetition research reversing scanf segmentationfault sequential shape socket socketprograming standard string systemcall threads turboc unix user voidmain() wab windows.h windowsapi
