 Given an array of positive numbers, find the maximum subsequence sum <= given sum, such that no two elements are adjacent to each other

This is my code

``````#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
int n;
ll sum;
vector<ll> v;
cin>>n;
ll a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
cin>>sum;
ll ans = 0;
ll inc = a;
ll exc = 0;
ll prev = 0;
for(int i=1;i<n;i++){
prev = inc;
inc = max(exc+a[i],a[i]);
exc = max(prev,exc);
// cout<<inc<<" "<<exc<<endl;
ll ans1 = max(inc,exc);
if(ans1<=sum){
ans = max(ans1,ans);
}
}
cout<<ans<<endl;
return 0;
}
``````

It passes for few cases but not for all, for eg.

number of elements n = 6

elements a[n] = {5,5,10,100,10,5}

and sum = 25

the output is 15, but output should be 25 (5 + 10 + 10)

Can u find the efficient solution or approach to this problem?

3 Likes

I can think of recursive solution. But it would have exponential time complexity.

``````int sum,n;
ll best = -1;

void rec(int id, vi &a, int temp){
if(id>=n){
if(temp>=best && temp<=sum) best = sum;
return;
}
rec(id+2, a, temp+a[id]);  // if we include i'th we need to skip i+1'th
rec(id+1, a, temp);        // if we not include i'th we can take i+1'th
}

int main(){
cin>>n;
vi a(n);
for(int i=0;i<n;i++) cin>>a[i];
cin>>sum;
rec(0, a, 0);
cout<<best<<"\n";
}
``````

I think there might be some greedy or dp approach to solve it in linear time.

1 Like

@anon2040365 Thanks for the solution, but your solution is not correct, for eg. when sum =6 then the output should be 5 but the code is giving 6.

Check this https://ide.geeksforgeeks.org/fr6zjwouTg

Could you please correct the solution ?

It’s just a typo in this line change this best = sum to best = temp.

1 Like

apply memoization to the above recursive solution of @anon2040365 for better complexity as there are too many repetitive calls of recursion

@karnikjain_345 I don’t think memoization will help here.

Do you have information about the array size?

@denjell The array size can be 1000 - 10000.

See this
2 Likes

@shadab_shaikh1 No, this will find the max sum, but we are interested in max sum less than or equal to a given sum. I have used similar approach in my solution, but this is not giving the right answer.

DP Solution ->
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, sum;
cin >> n;
int ar[n];
for(int i=0; i<n; cin >> ar[i], i++);
cin >> sum;
int ans = 0, dp[n] = {0};
dp = ar;
dp = max(dp, ar);
// Corner Cases
if(dp <= sum && dp <= sum){
ans = max(dp, dp);
}
else{
if(dp <= sum)
ans = dp;
else
ans = 0;
}
for(int i=2; i<n; i++){
int k = max(dp[i-1], dp[i-2] + ar[i]);
if(k > sum)
dp[i] = dp[i-1]; //Assign previous DP state
else
dp[i] = k; //Else the best new answer

``````	if(dp[i] <= sum)
ans = max(dp[i], ans);
}
cout << ans << endl;
``````

}

I took dp[i] to include the ith element and dp[i] to exclude the ith element and output ans is max(dp[n-1],dp[n-1]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int n;
cin>>n;
ll int dp[n+1];
ll int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<=n;i++)
{
dp[i]=0;
dp[i]=0;
}

// for(int i=0;i<n;i++)
// cin>>a[i];

``````dp=a;
dp=a;
dp=a;
dp=a;
for(int i=2;i<n;i++)
{
dp[i]=a[i]+max(dp[i-2],dp[i-2]);
dp[i]=max(dp[i-1],dp[i-2]);

}

cout<<max(dp[n-1],dp[n-1]);
return 0;
``````

}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int n;
cin>>n;
ll int dp[n+1];
ll int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<=n;i++)
{
dp[i]=0;
dp[i]=0;
}

// for(int i=0;i<n;i++)
// cin>>a[i];

``````dp=a;
dp=a;
dp=a;
dp=a;
for(int i=2;i<n;i++)
{
dp[i]=a[i]+max(dp[i-2],dp[i-2]);
dp[i]=max(dp[i-1],dp[i-2]);

}

cout<<max(dp[n-1],dp[n-1]);
return 0;
``````

}

1 Like