This can be reduced to the standard subset sub problem. For algorithms
to solve it consider reading about it here,
http://en.wikipedia.org/wiki/Subset_sum_problem
This is my implementation for solving this problem provided the range
of values that the array can take is small(from 0 to MXSUM-1
Very Nice soln Dhritiman.
The solution to the standard LCS problem only needs O(n^2) time and O(n)
space.
And you have very intelligently solved its variation also in the same time
and space complexity.
I fell this is the correct solution.
Nikhil Jindal
On Tue, Aug 31, 2010 at 2:13 AM,
Does not work with negative nos.
@ Yan Wang,@Adam it worked for ur inputs.
With the input like a= {10,0,0,0}, k = 2
it will give 0, 0 as output.
-Code-
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class NondecreasingMaxsum {
// With
@Yan Wang..can u tel me wat u meant by saying the following :
And we know all the different numbers in A[...]. we put them in a
rigorously increasing sequence B[1..p], where B[1] B[2] ...
B[p-1] B[p], and for every i from 1 to n, A[i] can be found in
B[1..p].
--
You received this message
@Yan Wang..can u tel me wat u meant by saying the following :
And we know all the different numbers in A[...]. we put them in a
rigorously increasing sequence B[1..p], where B[1] B[2] ...
B[p-1] B[p], and for every i from 1 to n, A[i] can be found in
B[1..p].
--
You received this
Maybe I shoud use 'Levels' to express my idea.
For example, A={1,0,1,0,2,2,0}, there are 7 numbers and 3 levels which
is represented by an increasing array B={0,1,2}.
On Mon, Aug 30, 2010 at 7:14 AM, vikash jain vikash.ro...@gmail.com wrote:
@Yan Wang..can u tel me wat u meant by saying the
This is, drawing on the idea of LCS using DP. Think, this works.
Given array A[1..n] and k, fill up two more arrays ,
lcs[j] = max_{i=1 to j-1} lcs[i] , where A[i] = A[j]
maxPrevindex[j] = i , where A[i] is max among all A[i], such that A[i]
= A[j] and i ranging over 1 to j-1
This can be done
@ rahul i m not gettting u can plz eleborate ..more
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
@Rahul
#includestdio.h
#includestdlib.h
int nondecresing_maxsum(int *a,int n,int k)
{ int sum=0,i,count=k+1,prev_num=a[0],*dp,count1=0;;
dp=(int *)malloc(sizeof(int)*(k+1));
for(i=0;in;++i)
if(prev_num=a[i])
{ sum+=a[i];
prev_num=a[i];
@Adam
i ran the program with n=4 and k=2 and sequence as 2,3,999,
i got 10998(i.e999+).
plz check it
On Sat, Aug 28, 2010 at 10:25 AM, Adam wangyanadam1...@gmail.com wrote:
Actually, your code just considers the only non-decreasing subsequence
which starts from a[0] and is the most
Sorry, this is not a good example.
Try this:
Assuming the sequence is 2, 1, 1, 1 and k = 3. The correct answer will
be 1, 1, 1. Run your code and see the result.
On Sat, Aug 28, 2010 at 1:54 PM, satish satish@gmail.com wrote:
@Adam
i ran the program with n=4 and k=2 and sequence as
Dynamic Programming is an obvious direction of thinking and also the
solution to this problem.
As far, I can only figure out a 3-dimensional DP algo for this
problem, demonstrated as below:
Assuming that the original array is A[1..n], n is the number of all
the elements in the array.
And we know
Guys the problem is similar to lcs with just a little difference that
here we don't have to maximize the lenght of subsequence but we have
to maximize the sum for a given number of elements(k) which should be
in non-decreasing order.
ex :
input : 6 4 2 7 5 8 7 8 k=4
output : 6+7+8+8=29
--
For the sequence ABCADGH ACDH is a subsequence..
On Wed, Aug 25, 2010 at 10:02 PM, Vikas Kumar dev.vika...@gmail.com wrote:
can you define what here subsequence means?
On Wed, Aug 25, 2010 at 9:32 PM, Rahul rv.wi...@gmail.com wrote:
@Jaswanth
It will be really kind if you will state the
@ jashwant raj,rahul
i think we have to sort array in non-decreasing order e.g. increasing
order
1 way . 2,4,1,4,8,6,7,9 1,2,4,4,6,7,8,9 it will take max(nlogn)
time with best sorting algo... also if use counting sort it will take
(n+k) time
2.way else in unsorted array it will
@ bittu
input : 6 1 4 8 3 7k=2
output : 6 + 8 =14
it's not 7+8=15 which wud be the case if ul apply sorting and take k
largest elements.
if i got ur point correct.
Rahul Verma
NIT Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
@Jaswanth
It will be really kind if you will state the algorithm rather than
providing codes, as it is tedious.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe
can you define what here subsequence means?
On Wed, Aug 25, 2010 at 9:32 PM, Rahul rv.wi...@gmail.com wrote:
@Jaswanth
It will be really kind if you will state the algorithm rather than
providing codes, as it is tedious.
--
You received this message because you are subscribed to the Google
@Vikas: I want to know the same.
On Wed, Aug 25, 2010 at 10:02 PM, Vikas Kumar dev.vika...@gmail.com wrote:
can you define what here subsequence means?
On Wed, Aug 25, 2010 at 9:32 PM, Rahul rv.wi...@gmail.com wrote:
@Jaswanth
It will be really kind if you will state the algorithm rather
suppose we take an array like this
5,3, 2, 6,7, 4, 8,1, 0, 7, 9
Here 2, 6,7
4,8
and 7,9 are non decreasing sub sequences of array and we have to find sum
of those sub sequences which is maximum.
the sum of 2, 6,7 is 15.
sum of 4, 8 is 12,
and sum of 7, 9 is 16.
maximum sum is 16.
20 matches
Mail list logo
