# Challenge 37c — Editorial The player repeatedly picks a value, gains that value multiplied by how many times it appears (since picking it deletes all copies), and is forced to lose all elements equal to that value plus one and minus one. This is the classic "pick a number but not its neighbors" structure, identical to the House Robber pattern applied over distinct values. ## Solution 1: Recursion with Memoization ### Intuition - The first thing to notice is that once we decide to take a certain number, we might as well take every copy of it in one shot, because taking it deletes its neighbors anyway. - So the real decision is only about which distinct values to keep, and the points from a value equal that value times how many times it appears. - Taking a value forbids taking the value right above and right below it, which feels exactly like choosing numbers on a line where neighbors clash. - For each value we simply choose the better of two futures: skip it, or take it and jump two steps ahead. - Remembering the answer for each starting value avoids recalculating the same future again and again. ### Approach - Count how many times each number appears in the sequence. - Build a value where each position stores that number multiplied by its count of appearances. - Walk through the possible values and at each one decide to either skip it or take it and move two positions forward. - Store the best result for each position so it is computed only once. - The answer is the best result starting from the smallest possible value. ### Pseudocode ```pseudocode solve(a) { /* Find the largest value so we know the range to work with */ maxVal = maximum value in a /* Prepare a table that holds total points for each value */ /* points[v] = v multiplied by how many times v appears */ for each x in a { points[x] = points[x] + x } /* Memory table filled with a marker meaning not computed yet */ memo = array filled with -1 /* Start the recursive choice from the smallest value */ return recurse(1, maxVal, points, memo) } recurse(v, maxVal, points, memo) { /* Base case: nothing left to pick beyond the max value */ if v > maxVal { return 0 } /* If already solved for this value, reuse it */ if memo[v] != -1 { return memo[v] } /* Option one: skip the current value and move to the next */ skip = recurse(v + 1, maxVal, points, memo) /* Option two: take current value and jump two ahead to avoid neighbor */ take = points[v] + recurse(v + 2, maxVal, points, memo) /* Store and return the better of the two choices */ memo[v] = max(skip, take) return memo[v] } ``` ### Code Implementation **C++** ```cpp #include using namespace std; class solution { public: long long recurse(int v, int maxVal, vector& points, vector& memo) { if (v > maxVal) { return 0; } if (memo[v] != -1) { return memo[v]; } long long skip = recurse(v + 1, maxVal, points, memo); long long take = points[v] + recurse(v + 2, maxVal, points, memo); memo[v] = max(skip, take); return memo[v]; } long long maxPoints(vector& a) { int maxVal = 0; for (int x : a) { maxVal = max(maxVal, x); } vector points(maxVal + 3, 0); for (int x : a) { points[x] += x; } vector memo(maxVal + 3, -1); return recurse(1, maxVal, points, memo); } }; /* int main() { int n; cin >> n; vector a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } solution sol; cout << sol.maxPoints(a); return 0; } */ ``` **Python** ```python import sys sys.setrecursionlimit(300000) class solution: def maxPoints(self, a): maxVal = max(a) points = [0] * (maxVal + 3) for x in a: points[x] += x memo = [-1] * (maxVal + 3) def recurse(v): if v > maxVal: return 0 if memo[v] != -1: return memo[v] skip = recurse(v + 1) take = points[v] + recurse(v + 2) memo[v] = max(skip, take) return memo[v] return recurse(1) ''' n = int(input()) a = list(map(int, input().split())) sol = solution() print(sol.maxPoints(a)) ''' ``` **Java** ```java import java.util.*; class Solution { public static long recurse(int v, int maxVal, long[] points, long[] memo) { if (v > maxVal) { return 0; } if (memo[v] != -1) { return memo[v]; } long skip = recurse(v + 1, maxVal, points, memo); long take = points[v] + recurse(v + 2, maxVal, points, memo); memo[v] = Math.max(skip, take); return memo[v]; } public static long maxPoints(int[] a) { int maxVal = 0; for (int x : a) { maxVal = Math.max(maxVal, x); } long[] points = new long[maxVal + 3]; for (int x : a) { points[x] += x; } long[] memo = new long[maxVal + 3]; Arrays.fill(memo, -1); return recurse(1, maxVal, points, memo); } } /* public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = scanner.nextInt(); } System.out.println(Solution.maxPoints(a)); } } */ ``` **JavaScript** ```javascript class Solution { static maxPoints(a) { let maxVal = 0; for (const x of a) { maxVal = Math.max(maxVal, x); } const points = new Array(maxVal + 3).fill(0); for (const x of a) { points[x] += x; } const memo = new Array(maxVal + 3).fill(-1); function recurse(v) { if (v > maxVal) { return 0; } if (memo[v] !== -1) { return memo[v]; } const skip = recurse(v + 1); const take = points[v] + recurse(v + 2); memo[v] = Math.max(skip, take); return memo[v]; } return recurse(1); } } /* function main() { const fs = require("fs"); const data = fs.readFileSync(0, "utf8").trim().split(/\s+/); let idx = 0; const n = Number(data[idx++]); const a = new Array(n); for (let i = 0; i < n; i++) { a[i] = Number(data[idx++]); } console.log(Solution.maxPoints(a)); } main(); */ ``` ### Complexity Analysis - **Time Complexity:** `O(n + M)` where `M` is the maximum value in the array. Counting and the recursion each take linear time. - **Space Complexity:** `O(M)` for the points and memo arrays, plus recursion stack depth. ## Solution 2: Bottom-Up Dynamic Programming ### Intuition - We already know that taking a value forbids taking the value directly next to it, just like choosing houses that cannot be adjacent. - Instead of asking about the future with recursion, we can build the answer from the smallest value upward. - At each value we keep the best total we could have collected so far. - For every value the best total is either what we had at the previous value, or the points from this value added to what we had two values back. - Building it step by step avoids the recursion stack entirely and is very simple to reason about. ### Approach - Count the occurrences of each number and turn them into total points per value. - Create a running table where each position holds the best score achievable up to that value. - For each value take the larger of skipping it or taking it plus the best score two positions earlier. - Continue up to the largest value present in the sequence. - The final position holds the maximum points possible. ### Pseudocode ```pseudocode solve(a) { /* Determine the range of values we must consider */ maxVal = maximum value in a /* Accumulate total points earned for taking each value */ for each x in a { points[x] = points[x] + x } /* dp[v] stores the best score achievable using values up to v */ dp = array of size maxVal + 1 /* Base case: taking value one gives its full points */ dp[0] = 0 dp[1] = points[1] /* Fill the table from small values to large values */ for v = 2 to maxVal { /* Best is either skip current or take current plus dp two back */ dp[v] = max(dp[v - 1], dp[v - 2] + points[v]) } /* The last entry holds the overall maximum score */ return dp[maxVal] } ``` ### Code Implementation **C++** ```cpp #include using namespace std; class solution { public: long long maxPoints(vector& a) { int maxVal = 0; for (int x : a) { maxVal = max(maxVal, x); } vector points(maxVal + 1, 0); for (int x : a) { points[x] += x; } vector dp(maxVal + 1, 0); dp[0] = 0; if (maxVal >= 1) { dp[1] = points[1]; } for (int v = 2; v <= maxVal; v++) { dp[v] = max(dp[v - 1], dp[v - 2] + points[v]); } return dp[maxVal]; } }; /* int main() { int n; cin >> n; vector a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } solution sol; cout << sol.maxPoints(a); return 0; } */ ``` **Python** ```python class solution: def maxPoints(self, a): maxVal = max(a) points = [0] * (maxVal + 1) for x in a: points[x] += x dp = [0] * (maxVal + 1) if maxVal >= 1: dp[1] = points[1] for v in range(2, maxVal + 1): dp[v] = max(dp[v - 1], dp[v - 2] + points[v]) return dp[maxVal] ''' n = int(input()) a = list(map(int, input().split())) sol = solution() print(sol.maxPoints(a)) ''' ``` **Java** ```java import java.util.*; class Solution { public static long maxPoints(int[] a) { int maxVal = 0; for (int x : a) { maxVal = Math.max(maxVal, x); } long[] points = new long[maxVal + 1]; for (int x : a) { points[x] += x; } long[] dp = new long[maxVal + 1]; dp[0] = 0; if (maxVal >= 1) { dp[1] = points[1]; } for (int v = 2; v <= maxVal; v++) { dp[v] = Math.max(dp[v - 1], dp[v - 2] + points[v]); } return dp[maxVal]; } } /* public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = scanner.nextInt(); } System.out.println(Solution.maxPoints(a)); } } */ ``` **JavaScript** ```javascript class Solution { static maxPoints(a) { let maxVal = 0; for (const x of a) { maxVal = Math.max(maxVal, x); } const points = new Array(maxVal + 1).fill(0); for (const x of a) { points[x] += x; } const dp = new Array(maxVal + 1).fill(0); if (maxVal >= 1) { dp[1] = points[1]; } for (let v = 2; v <= maxVal; v++) { dp[v] = Math.max(dp[v - 1], dp[v - 2] + points[v]); } return dp[maxVal]; } } /* function main() { const fs = require("fs"); const data = fs.readFileSync(0, "utf8").trim().split(/\s+/); let idx = 0; const n = Number(data[idx++]); const a = new Array(n); for (let i = 0; i < n; i++) { a[i] = Number(data[idx++]); } console.log(Solution.maxPoints(a)); } main(); */ ``` ### Complexity Analysis - **Time Complexity:** `O(n + M)` - **Space Complexity:** `O(M)` ## Solution 3: Space-Optimized Dynamic Programming ### Intuition - Looking at the step-by-step version, each new best score depends only on the two values right before it. - That means we never truly need the entire table, only the last two computed totals. - We can slide two variables forward as we move through the values and keep updating them. - This keeps the exact same logic but throws away memory we no longer need. - It is the leanest form of the same idea and runs just as fast. ### Approach - Count the occurrences of each number and convert them to total points per value. - Keep two running values representing the best scores two steps back and one step back. - For each value compute the new best as the larger of skipping or taking it. - Shift the two running values forward after each step. - After processing the largest value the last running value is the answer. ### Pseudocode ```pseudocode solve(a) { /* Find the range of values present */ maxVal = maximum value in a /* Convert counts into total points per value */ for each x in a { points[x] = points[x] + x } /* prev2 is best two values back, prev1 is best one value back */ prev2 = 0 prev1 = 0 /* Move through every value from smallest to largest */ for v = 1 to maxVal { /* Best current is skip prev1 or take current plus prev2 */ cur = max(prev1, prev2 + points[v]) /* Slide the window forward for the next value */ prev2 = prev1 prev1 = cur } /* prev1 now holds the overall maximum score */ return prev1 } ``` ### Code Implementation **C++** ```cpp #include using namespace std; class solution { public: long long maxPoints(vector& a) { int maxVal = 0; for (int x : a) { maxVal = max(maxVal, x); } vector points(maxVal + 1, 0); for (int x : a) { points[x] += x; } long long prev2 = 0, prev1 = 0; for (int v = 1; v <= maxVal; v++) { long long cur = max(prev1, prev2 + points[v]); prev2 = prev1; prev1 = cur; } return prev1; } }; /* int main() { int n; cin >> n; vector a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } solution sol; cout << sol.maxPoints(a); return 0; } */ ``` **Python** ```python class solution: def maxPoints(self, a): maxVal = max(a) points = [0] * (maxVal + 1) for x in a: points[x] += x prev2, prev1 = 0, 0 for v in range(1, maxVal + 1): cur = max(prev1, prev2 + points[v]) prev2 = prev1 prev1 = cur return prev1 ''' n = int(input()) a = list(map(int, input().split())) sol = solution() print(sol.maxPoints(a)) ''' ``` **Java** ```java import java.util.*; class Solution { public static long maxPoints(int[] a) { int maxVal = 0; for (int x : a) { maxVal = Math.max(maxVal, x); } long[] points = new long[maxVal + 1]; for (int x : a) { points[x] += x; } long prev2 = 0, prev1 = 0; for (int v = 1; v <= maxVal; v++) { long cur = Math.max(prev1, prev2 + points[v]); prev2 = prev1; prev1 = cur; } return prev1; } } /* public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = scanner.nextInt(); } System.out.println(Solution.maxPoints(a)); } } */ ``` **JavaScript** ```javascript class Solution { static maxPoints(a) { let maxVal = 0; for (const x of a) { maxVal = Math.max(maxVal, x); } const points = new Array(maxVal + 1).fill(0); for (const x of a) { points[x] += x; } let prev2 = 0, prev1 = 0; for (let v = 1; v <= maxVal; v++) { const cur = Math.max(prev1, prev2 + points[v]); prev2 = prev1; prev1 = cur; } return prev1; } } /* function main() { const fs = require("fs"); const data = fs.readFileSync(0, "utf8").trim().split(/\s+/); let idx = 0; const n = Number(data[idx++]); const a = new Array(n); for (let i = 0; i < n; i++) { a[i] = Number(data[idx++]); } console.log(Solution.maxPoints(a)); } main(); */ ``` ### Complexity Analysis - **Time Complexity:** `O(n + M)` - **Space Complexity:** `O(M)` for the points table, but only `O(1)` additional space for the rolling variables. ## Tags - Array - Hash Table - Dynamic Programming