Is this correct ? By sorting you loose the order, right.
Take A= [5,2,6,1,5] k=11
Correct answer = [5,5] or [2,6] or [1,5]
By sorting you get, [1,2,5,5,6] and produce [1,2,5] as the answer which is
not a subsequence.
Here is an approach.
Given a array A[1..N] , compute LCS[j] for all j in [1..N]
If the subsequence is not to be continuous then
sort the given array. O(nlogn)
and then go on adding from the least element until the sum gets >= k
and then denote the array elements till the previous one as the set of
desired elements. O(n)
Total complexity O(nlogn).
- Abhirup
On Tue, Aug 17,
You have to return the length of the subsequence with longest length and sum
< K . If there are multiple solutions report anyone.
On Wed, Aug 18, 2010 at 12:40 PM, srinivas reddy
wrote:
> sorry man to say that in your example so many solutions exist and one more
> thing is problem is not clear tr
sorry man to say that in your example so many solutions exist and one more
thing is problem is not clear try to give clear idea
On Tue, Aug 17, 2010 at 11:47 PM, amit wrote:
> Given an array, find the longest subarray which the sum of the
> subarray less or equal then the given MaxSum
> int[] Fi
Given an array, find the longest subarray which the sum of the
subarray 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}
--
You received this message because you are sub
