745. Brainpower Exam
A quiz show presents its challenges in a fixed order. Row i of questions is [reward, lockout]: attempting challenge i earns reward points, but the contestant must then sit out the next lockout challenges and cannot attempt them. Any challenge may also be skipped, and a skipped challenge costs nothing.
Challenges are faced strictly from first to last, and a decision on a challenge is final once the next one appears. Return the maximum total reward the contestant can collect. A lockout reaching past the last challenge simply ends the show. The result needs 64-bit arithmetic.
Aim for time O(n) and space O(n), where n is the number of rows.
Example 1
- Input:
- questions = [[4,1],[9,2],[3,0],[6,1],[2,0]]
- Output:
- 13
- Explanation:
Take the first (4 points, locks out the 9), then the third (3) and the fourth (6): 13 points, which beats taking the 9 and then only the last question.
Example 2
- Input:
- questions = [[5,4],[1,0],[1,0],[8,0]]
- Output:
- 10
- Explanation:
Attempting the first locks out everything else for 5 points; skipping it and taking the last three gives 1 + 1 + 8 = 10.
Example 3
- Input:
- questions = [[2,0],[2,0],[2,0]]
- Output:
- 6
- Explanation:
No lockouts, so all three are taken for 6 points.
Constraints
1 ≤ questions.length ≤ 105
questions[i].length == 2
1 ≤ reward ≤ 109, 0 ≤ lockout ≤ 105
The answer is below 9 * 1015.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)