Maximize Sum of Device Ratings - Solution & Explanation

Problem Overview: You are given an array representing device ratings. Activating certain devices may restrict activating adjacent ones, so the goal is to choose a subset of devices that maximizes the total rating while respecting the constraint.

Approach 1: Brute Force Recursion (Exponential Time, O(2^n) time, O(n) space)

Try every possible subset of devices. At each index, you either activate the current device or skip it. If you activate it, the next device cannot be chosen, so the recursion jumps two indices forward. If you skip it, continue with the next index. This approach explores the full decision tree and guarantees the correct answer, but the repeated recalculation of overlapping subproblems causes exponential runtime.

Approach 2: Dynamic Programming with Memoization (O(n) time, O(n) space)

The recursive solution repeatedly solves the same states. Store results in a memo array where dp[i] represents the maximum rating achievable starting from index i. For each position, compute max(rating[i] + dp[i+2], dp[i+1]). Each state is evaluated once, reducing complexity to linear time. This method clearly exposes the overlapping subproblem structure typical in dynamic programming problems.

Approach 3: Bottom-Up DP (O(n) time, O(n) space)

Instead of recursion, build the solution iteratively. Define dp[i] as the best sum achievable considering the first i devices. The transition becomes dp[i] = max(dp[i-1], dp[i-2] + rating[i]). Iterate through the array once while maintaining this relationship. This version avoids recursion overhead and is easier to reason about during interviews. The approach relies on recognizing optimal substructure within the array.

Approach 4: Space Optimized DP (O(n) time, O(1) space)

The DP transition only depends on the previous two states. Instead of maintaining the entire DP array, track two variables representing dp[i-1] and dp[i-2]. For each device rating, compute the new best value and shift the variables forward. This keeps memory usage constant while preserving the same linear runtime. The logic mirrors classic patterns seen in many dynamic programming optimization problems.

Recommended for interviews: Start by describing the brute force choice of picking or skipping a device to show understanding of the problem structure. Then transition to dynamic programming, which interviewers typically expect. The space‑optimized DP solution demonstrates strong problem‑solving ability because it recognizes that only two previous states are required.