Geek's Training
Geek's Training is a medium dynamic programming problem solved with the 2d dp - max/min of last row pattern.
The best approach, optimal (dp over days with 3 states), runs in O(n · 9) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from recursion with the last activity up.
Problem
Over n days, each day you do one of three activities, earning arr[day][activity] points. You cannot repeat the same activity on consecutive days. Return the maximum total points.
Examples
Example 1
- Input
arr = [[1,2,5],[3,1,1],[3,3,3]]- Output
11- Why
- Day 1 activity 2 (5), day 2 activity 0 (3), day 3 activity 1 or 2 (3).
Example 2
- Input
arr = [[1,1,1],[2,2,2],[3,3,3]]- Output
6
Constraints
1 <= n <= 10^5; 3 activities per day; points 1 to 100.- You cannot do the same activity on two consecutive days.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Recursion with the last activity | O(3 · 2ⁿ) | O(n) |
| Optimal (DP over days with 3 states) | O(n · 9) | O(1) |
1Recursion with the last activity
O(3 · 2ⁿ)O(n)solve(day, last) = the best over activities a != last of points[day][a] + solve(day - 1, a).
- Base day 0: max over a != last.
class Solution {
public int maximumPoints(int[][] arr) {
return solve(arr, arr.length - 1, 3);
}
private int solve(int[][] p, int day, int last) {
int best = 0;
for (int a = 0; a < 3; a++) {
if (a == last) continue;
int v = p[day][a] + (day == 0 ? 0 : solve(p, day - 1, a));
best = Math.max(best, v);
}
return best;
}
}class Solution:
def maximumPoints(self, arr: List[List[int]]) -> int:
return self.solve(arr, len(arr) - 1, 3)
def solve(self, p: List[List[int]], day: int, last: int) -> int:
best = 0
for a in range(3):
if a == last:
continue
v = p[day][a] + (0 if day == 0 else self.solve(p, day - 1, a))
best = max(best, v)
return bestclass Solution {
public:
int maximumPoints(vector<vector<int>>& arr) {
return solve(arr, arr.size() - 1, 3);
}
private:
int solve(vector<vector<int>>& p, int day, int last) {
int best = 0;
for (int a = 0; a < 3; a++) {
if (a == last) continue;
int v = p[day][a] + (day == 0 ? 0 : solve(p, day - 1, a));
best = max(best, v);
}
return best;
}
};function maximumPoints(arr) {
function solve(p, day, last) {
let best = 0;
for (let a = 0; a < 3; a++) {
if (a === last) continue;
const v = p[day][a] + (day === 0 ? 0 : solve(p, day - 1, a));
best = Math.max(best, v);
}
return best;
}
return solve(arr, arr.length - 1, 3);
}2Optimal (DP over days with 3 states)
O(n · 9)O(1)prev[a] = best total up to yesterday if yesterday's activity was a. Today's cur[a] = points[day][a] + max of prev over the other two activities. The answer is max over the last day.
- prev = points[0].
- cur[a] = p[d][a] + max(prev[b]) for b != a.
- Return max(prev) at the end.
class Solution {
public int maximumPoints(int[][] arr) {
int[] prev = arr[0].clone();
for (int d = 1; d < arr.length; d++) {
int[] cur = new int[3];
for (int a = 0; a < 3; a++) {
int best = 0;
for (int b = 0; b < 3; b++) if (b != a) best = Math.max(best, prev[b]);
cur[a] = arr[d][a] + best;
}
prev = cur;
}
return Math.max(prev[0], Math.max(prev[1], prev[2]));
}
}class Solution:
def maximumPoints(self, arr: List[List[int]]) -> int:
prev = arr[0][:]
for d in range(1, len(arr)):
cur = [0] * 3
for a in range(3):
best = 0
for b in range(3):
if b != a:
best = max(best, prev[b])
cur[a] = arr[d][a] + best
prev = cur
return max(prev[0], prev[1], prev[2])class Solution {
public:
int maximumPoints(vector<vector<int>>& arr) {
vector<int> prev = arr[0];
for (int d = 1; d < (int)arr.size(); d++) {
vector<int> cur(3, 0);
for (int a = 0; a < 3; a++) {
int best = 0;
for (int b = 0; b < 3; b++) if (b != a) best = max(best, prev[b]);
cur[a] = arr[d][a] + best;
}
prev = cur;
}
return max(prev[0], max(prev[1], prev[2]));
}
};function maximumPoints(arr) {
let prev = arr[0].slice();
for (let d = 1; d < arr.length; d++) {
const cur = new Array(3).fill(0);
for (let a = 0; a < 3; a++) {
let best = 0;
for (let b = 0; b < 3; b++) if (b !== a) best = Math.max(best, prev[b]);
cur[a] = arr[d][a] + best;
}
prev = cur;
}
return Math.max(prev[0], Math.max(prev[1], prev[2]));
}Edge cases to test
- A single day (take the max)
Hints
Hint 1
The state is (day, last activity). dp[d][a] = best total up to day d if day d's activity is a.
FAQ
What is the best time complexity for Geek's Training?
Optimal (DP over days with 3 states) runs in O(n · 9) time and O(1) extra space.
Which pattern does Geek's Training use?
It is a dynamic programming problem that uses the 2d dp - max/min of last row pattern. Other problems with the same pattern: Minimum Falling Path Sum, Triangle.
Is there a brute force solution for Geek's Training?
Yes. Recursion with the last activity takes O(3 · 2ⁿ) time and O(n) space. solve(day, last) = the best over activities a != last of points[day][a] + solve(day - 1, a).
Which edge cases should I test for Geek's Training?
A single day (take the max).