Author |
Topic: Longest SubSequence with Sum <= K (Read 6222 times) |
|
sateesp
Newbie
Gender: 
Posts: 35
|
 |
Longest SubSequence with Sum <= K
« on: Sep 4th, 2010, 12:20pm » |
 Quote  Modify
|
Given an array, find the longest sub set whose sum is less or equal then the given MaxSum
int[] FindMaxSumArray(int[] array, int maxsum)
for example, given array: {1, -2, 4, 5, -2, 6, 7}
maxsum=7
The result would be: {1,-2, -2, 6}
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Longest SubSequence with Sum <= K
« Reply #1 on: Sep 4th, 2010, 1:08pm » |
Quote Modify
|
Sort the array, and the take the smallest numbers that sum to less than or equal the maxsum.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Longest SubSequence with Sum <= K
« Reply #2 on: Sep 8th, 2010, 5:13am » |
Quote Modify
|
The *longest* subset?
Wouldn't {1, -2, 4, 5, -2} (sum 6) be longer?
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Longest SubSequence with Sum <= K
« Reply #3 on: Sep 11th, 2010, 2:04am » |
Quote Modify
|
on Sep 8th, 2010, 5:13am, Grimbal wrote:The *longest* subset?
Wouldn't {1, -2, 4, 5, -2} (sum 6) be longer?
|
|
Yes, i think {1, -2, 4, 5, -2} this should be the set.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
MrLambert
Newbie
Posts: 13
|
|
Re: Longest SubSequence with Sum <= K
« Reply #4 on: Oct 31st, 2011, 9:40am » |
Quote Modify
|
Yes, its a mistake
set should be: {1, -2, 4, 5, -2}
|
|
IP Logged |
|
|
|
computing
Newbie
Gender:
Posts: 2
|
|
Re: Longest SubSequence with Sum <= K
« Reply #5 on: Nov 7th, 2011, 2:01am » |
Quote Modify
|
One simple way is to use Kadane's algorithm and keep verifying input constraints, in such a way that the sum_so_far should be less than MaxSum, if so, consider next element. Otherwise, current indices [i, j] of sum_so_far will be answer. A DP solution.
We may need to repeat the procedure for all those sub array sizes that are less than current sub array that satisfies input constraints. I mean, we also need to check the remaining array [j+1, n], if (n - j) > (j - i + 1).
Kadane algorithm - http://en.wikipedia.org/wiki/Maximum_subarray_problem
Any thoughts?
|
| « Last Edit: Nov 7th, 2011, 2:02am by computing » |
IP Logged |
|
|
|
kaka
Newbie
Gender:
Posts: 24
|
|
Re: Longest SubSequence with Sum <= K
« Reply #6 on: Nov 28th, 2011, 11:40pm » |
Quote Modify
|
@computing: Kadane's algorithm is about finding the contiguous subarray where as this one is about sub set (order doesn't matter)
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print