[algogeeks] Re: sum of subsequence

On Jul 4, 2:16 pm, jalaj jaiswal wrote: > find the subsequence in an array which sum to k This equivalent to the subset sum problem, which is weakly NP-hard. See http://en.wikipedia.org/wiki/Subset_sum_problem for a pseudo-poly time DP algorithm. A related, interesting problem is to find a sub_r

[algogeeks] Re: sum of subsequence

for (int i=0; i wrote: > find the subsequence in an array which sum to k > > -- > With Regards, > Jalaj Jaiswal > +919026283397 > B.TECH IT > IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to

[algogeeks] Re: sum of subsequence.

On Oct 9, 8:56 am, ankur aggarwal wrote: > 2. Given an array all of whose elements are positive numbers, find the > maximum sum of a subsequence with the constraint that no 2 numbers in the > sequence should be adjacent in the array. > >  i) 3 2 7 10 should return 13 (sum of 3 and 10) > > ii) 3

[algogeeks] Re: sum of subsequence.

#include using namespace std; int maxsum(int a[], int n) { int prevmaxsum=0; int currmaxsum=a[0]; int last=0,temp=0; for(int i=1;icurrmaxsum) { temp=a[i]+prevmaxsum; prevmaxsum=currmaxsum; currmaxsum=temp; last=i; cout > 2. Given an array all

[algogeeks] Re: sum of subsequence.

This is a simple dp problem . define for each i following 2 quantities : best1[i] : best sum in similar constraint of first i elements only when last ( ith ) term is always included best2[i] : best sum in similar constraint of the first i elements only when last (ith ) term is NOT included so we