[Google Hiring Test] Maximum sum subsequence with no adjacent elements

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
click here to see its working in IDE

#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[0];
    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 :sweat_smile:
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[0] = ar[0];
dp[1] = max(dp[0], ar[1]);
// Corner Cases
if(dp[0] <= sum && dp[1] <= sum){
ans = max(dp[0], dp[1]);
}
else{
if(dp[0] <= sum)
ans = dp[0];
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;

}

How about this solution: =>

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

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

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

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

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

}

How about this solution. ???

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

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

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

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

}

1 Like