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

help
1

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
2

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
3

@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 Online Compiler and IDE - GeeksforGeeks

Could you please correct the solution ?

4

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

1 Like
5

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

6

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

7

Do you have information about the array size?

8

@denjell The array size can be 1000 - 10000.

9

See this
2 Likes
10

@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.

11

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;

}

12

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;

}

13

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
14

If we ignore the <= sum conditional and just try to find the max sum with no adjecent elements, I have a question.

In this, we are taking the max between the sum of the ith element of array plus the i-2th element of dp array and the i-1th element of the dp array. But it could be the case that the i-1th element was not used to make the sum at dp[i-1]. If that is the case, we could technically add the ith element to this too right? Can someone explain why this isn’t necessary?