Why isn't this code working

#1

I maintained a bool plays[n] array which will keep a track of whether the player played in a particular day or not. int dp[n] is also maintained where dp[i] denotes the maximum payment till the ith match.

For the recurrence two cases arise:

  1. The player has been playing for the last two consecutive days. This gives rise to three cases:
  1. payment[i] > payment[i-1] : in this case I put plays[i-1] = false and include ith day.
  2. payment[i] > payment[i-2] : in this cases the (i-2)th day is removed and ith day is included.
  3. This is the case where ith day is not considered at all.
  1. The player is not playing for last two consecutive days and hence the payment[i] is added to dp[i] and plays[i]=true.

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long

int32_t main () {
	int n;
	cin>>n;
	vector<int> pay(n);
	for(int i=0;i<n;i++) {
		cin>>pay[i];
	}
	vector<int> dp(n);
	vector<bool> plays(n,true);
	dp[0] = pay[0];
	dp[1] = pay[1] + pay[0];

	for(int i=2;i<n;i++) {
		if(plays[i-1] && plays[i-2]) {
			if(pay[i] > pay[i-2]) {
				dp[i] = dp[i-1] - pay[i-2] + pay[i];
				plays[i-2] = false;
			} else if(pay[i] > pay[i-1]) {
				dp[i] = dp[i-1] - pay[i-1] + pay[i];
				plays[i-1] = false;
			} else {
				dp[i] = dp[i-1];
				plays[i] = false;
			}
		} else {
			dp[i] = dp[i-1] + pay[i];
		}
	}
	 cout<<dp[n-1]<<endl;
	//for(int i:dp) {
	//	cout<<i<<" ";
	//}
	return 0;
}
#2

@piyush14298 hey your dp array is not filled properly please check that.

#3

I am not able to figure out that. Can you please explain exactly where is the problem? Is the logic wrong or there is some mistake in the code?

#4

@piyush14298 hehy there is problem in dp logic check this I have corrected it with comments:

1 Like
#5

Got it. Thanks a lot for such a nice code.

#6

@piyush14298 no problem bro, glad you get it. Happy coding :slight_smile:

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.