# Boredom Problem – Dynamic Programming Solutions

«
»

This is a C++ Program that Solves Boredom Problem using Dynamic Programming technique.

Problem Description

Alex doesn’t like boredom. That’s why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it.

Given a sequence a consisting of n integers. The player can make several steps. In a single step he can choose an element of the sequence (let’s denote it a[k]) and delete it, at that all elements equal to a[k] + 1 and a[k] - 1 also must be deleted from the sequence. That step brings ak points to the player.

Alex is a perfectionist, so he decided to get as many points as possible. Help him.

Problem Solution

The problem is to find the maximum points that can be collected with the given constraints. This can be solved with Dynamic Programming. First, we read all the values and group them.

For example – If the values are 2 1 3 4 2 3 4, we group all 1’s together, all 2’s together and so on. This way we will be able to find frequency of each number. In this example, If 2 is selected in the final solution, then its total contribution will be 4 (number*its frequency).

Now, we create a array dp[] to memoize values. dp[i]=maximum points that can be collection using only i distict values. We will proceed in bottom up manner- first calculating dp[1], dp[2], …, dp[n].

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

If there are n distinct values in the input, the answer will be given by dp[n].

Expected Input and Output

Case-1:

```
a[]={1, 2, 3}
Expected answer=4 by collecting 1 and 3 (2 has to be deleted)```

Case-2:

```
a[]={1, 2, 1, 3, 2, 2, 2, 2, 3}
Expected answer=10 by collecting all 2's (1 and 3 will be deleted)```

Case-3:

```a[]={5, 3, 4, 2, 3, 7, 2}
Expected answer=18 by collecting 3, 5 and 7```
Program/Source Code

Here is source code of the C++ Program to Boredom problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

advertisement
1. ` `
2. `//boredom dp`
3. `#include <bits/stdc++.h>`
4. `using namespace std;`
5. ` `
6. `int main()`
7. `{`
8. `    int i,j;`
9. `    int n;`
10. `    long long x,y;`
11. ` `
12. `    cout<<"How many values ?"<<endl;`
13. `    cin>>n;`
14. ` `
15. `    //map to store value and its frequency`
16. `    map<int,int> mp;`
17. `    map<int, int> :: iterator it;`
18. ` `
19. `    cout<<"Enter the values "<<endl;`
20. ` `
21. `    //input all values`
22. `    for(i=0;i<n;i++)`
23. `    {`
24. `        cin>>j;`
25. ` `
26. `        if(mp.find(j)!=mp.end())`
27. `        {`
28. `            //increase frequency by 1`
29. `            mp[j]++;`
30. `        }`
31. ` `
32. `        else`
33. `        {`
34. `            mp[j]=1;`
35. `        }`
36. `    }`
37. ` `
38. `    n=mp.size();`
39. ` `
40. `    //array to memoize values `
41. `    vector<pair<int,long long int> > dp(mp.size()+1);`
42. ` `
43. `    //initialize`
44. `    dp[0].first=0;`
45. `    dp[0].second=0;`
46. ` `
47. `    for(it=mp.begin(),i=1;it!=mp.end();i++,it++)`
48. `    {`
49. `        dp[i].first=it->first;`
50. ` `
51. `        x=it->first;`
52. `        y=it->second;`
53. ` `
54. `        dp[i].second=x*y;`
55. `    }`
56. ` `
57. `    //implement DP in bottom up manner    `
58. `    for(i=2;i<=n;i++)`
59. `    {`
60. `        //select previous value`
61. `        j=i-1;`
62. ` `
63. `        if(dp[i].first==(dp[j].first+1))`
64. `        {`
65. `            j--;`
66. `        }`
67. ` `
68. `        //now add`
69. `        dp[i].second+=dp[j].second;`
70. ` `
71. `        //compare`
72. `        dp[i].second=max(dp[i].second,dp[i-1].second);`
73. `    }`
74. ` `
75. `    //result`
76. `    cout<<"The answer is "<<dp[n].second<<endl;`
77. ` `
78. `    return 0;`
79. `}`
Program Explanation

main() – In the main function, we take the value of n(number of integers) and then input the array of size n. The result is displayed at the standard output.

Runtime Test Cases
```
Case-1:
\$ g++ boredom.cpp
\$ ./a.out
How many values ?
3
Enter the values
1 2 3
The answer is 4

Case-2:
\$ ./a.out
How many values ?
9
Enter the values
1 2 1 3 2 2 2 2 3
The answer is 10

Case-3:
\$ ./a.out
How many values ?
7
Enter the values
5 3 4 2 3 7 2
The answer is 18```

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.