# 5 Lines Easy DP solution in C++

• Given in problem that if we choose N then N-1 and N+1 should be deleted. In other way it means if we want to pick i , then maximum sum till 'i' will be maximum of('sum till i-2 + frequency of ith element * i' ,'sum till i-1'). This gives easy DP expression as
*'dp[i] = max(dp[i-1],dp[i-2]+(cnt[i]i))'

where array 'cnt[]' holds count of 'i' in array 'nums' . i.e 'i' will contribute 'i*cnt[i]' in total sum;
and dp[i] holds maximum sum till i

``````class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
vector<int> cnt(10009,0);
int n = nums.size();

for(int i=0;i<n;i++)cnt[nums[i]]++;// store the frequency of i'th element of nums in array cnt

vector<int> dp(10009,0);

dp[1] = cnt[1]*1;// as maximum sum till 1 will be cnt[1] i.e frequency of 1 in nums[]

for(int i=2;i<=10000;i++)
{
dp[i]=max(dp[i-1],dp[i-2]+(cnt[i]*i));//maximum sum till i'th element according to above dp expression
}
return dp[10000];
}
};
``````

• Um... how is that "5 Lines"?

• @ManuelP
if you dont count function signature, variable declaration , its of 5 lines only

``````line 1: for(int i=0;i<n;i++)cnt[nums[i]]++;
line 2: dp[1] = cnt[1]*1;
line 3: for(int i=2;i<=10000;i++)
line 4: dp[i]=max(dp[i-1],dp[i-2]+(cnt[i]*i));
line 5: return dp[10000];
``````

just count the algorithmic steps only

• @shaeli Hmm, not counting the signature is common (regarded as part of the question, not part of the actual solution), but not counting your own variable declarations (and even non-default definitions!) is very uncommon and unexpected, so this is rather misleading...

• Btw, better don't format everything as code, makes your explanation hard to read, especially the need to scroll it sideways.

Oh and you're accessing `dp[i-2]` even when `i = 1`, i.e., `dp[-1]`. That's not good.

• Given in problem that if we choose N then N-1 and N+1 should be deleted. In other way it means if we want to pick i , then maximum sum till 'i' will be maximum of('sum till i-2 + frequency of ith element * i' ,'sum till i-1'). This gives easy DP expression as
*'dp[i] = max(dp[i-1],dp[i-2]+(cnt[i]i))'

where array 'cnt[]' holds count of 'i' in array 'nums' . i.e 'i' will contribute 'i*cnt[i]' in total sum;
and dp[i] holds maximum sum till i

``````class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
vector<int> cnt(10009,0);
int n = nums.size();

for(int i=0;i<n;i++)cnt[nums[i]]++;// store the frequency of i'th element of nums in array cnt

vector<int> dp(10009,0);

dp[1] = cnt[1]*1;// as maximum sum till 1 will be cnt[1] i.e frequency of 1 in nums[]

for(int i=2;i<=10000;i++)
{
dp[i]=max(dp[i-1],dp[i-2]+(cnt[i]*i));//maximum sum till i'th element according to above dp expression
}
return dp[10000];
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.