for (int i=0; iarr.size(); i++) {
int sum=0;
for (int j=i; jarr.size() sum=k ; j++)
sum = sum + arr[j];
if (sum == k) break;
}
An O(n^2) solution (Just to prove that a solution does exist even
though a little inefficient).
Can we at least improve upon the above algo to remove
On Jul 4, 2:16 pm, jalaj jaiswal jalaj.jaiswa...@gmail.com 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
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
#includeiostream
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;in;i++)
{
if(last!=(i-1))
{
prevmaxsum=currmaxsum;
currmaxsum=a[i]+prevmaxsum;
last=i;
On Oct 9, 8:56 am, ankur aggarwal ankur.mast@gmail.com 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
