➤ Problem Link : 455A. Boredom
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int arr[n+1];
long long int dp[n+1];
for(int i=1;i<=n;i++)
cin>>arr[i];
arr[0]=0;
dp[0]=0;
sort(arr,arr+n+1);
long long int prevSum=0;
long long int ans=0;
for(int i=1;i<=n;i++)
{
if(arr[i]==arr[i-1])
dp[i]=arr[i]+dp[i-1];
else if(arr[i]>arr[i-1]+1)
{
dp[i]=arr[i]+max(prevSum,dp[i-1]);
prevSum=max(prevSum,dp[i-1]);
}
else
{
dp[i]=arr[i]+prevSum;
prevSum=max(prevSum,dp[i-1]);
}
// cout<<i<<" "<<arr[i]<<" "<<dp[i]<<endl;
ans=max(ans,dp[i]);
}
cout<<ans;
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.