Alice and Bob Explanation

#1

I am not able to understand how the condition is checked and how are the transitions happening, would help if tree could be made.

#2

If we arrange the number in groups, and in increasing order.
We have 2 options, either to take i’th group, and dp[i-2] //so we skipped i-1’th group.
or we can skip i’th group and take dp[i-1]
or we can take dp[i-1]

int N;
cin>>N;
long long arr[200001]={0};
for(int i=0;i<N;i++)
{
    int temp;
    cin>>temp;
    arr[temp]++;
}
long long dp[200001]={0};
dp[0]=0;
dp[1]=arr[1];
for(int i=2;i<=200000;i++)
    dp[i]=max(arr[i]*i+dp[i-2],dp[i-1]);
cout<<dp[200000];
1 Like