Problem Statement
You are given two integer arrays:
For every day, we can choose one of three options:
Do no task.
Perform a low-effort task.
Perform a high-effort task.
The important condition is:
A high-effort task can be performed only on the first day or when no task was performed on the previous day.
We need to find the maximum total number of tasks that can be completed.
Example
Consider:
h = [2, 8, 1]
l = [1, 2, 1]
One possible selection is:
Day 0 → High effort = 2
Day 1 → No task
Day 2 → High effort = 1
Total:
2 + 1 = 3
But a better choice is:
Day 0 → Low effort = 1
Day 1 → High effort = 8
Total:
1 + 8 = 9
Therefore:
h = [2, 8, 1]
l = [1, 2, 1]
Output = 9
The important constraint is that high effort requires the previous day to have no task.
Dynamic Programming Idea
The brute-force approach would try every possible choice for every day.
For each day:
No task
Low effort
High effort
This gives roughly 3^n possibilities, which is far too expensive for:
n <= 100000
Instead, we use Dynamic Programming (DP).
The main observation is to consider the choices available on the current day.
If We Perform a Low-Effort Task Today
There is no restriction on what we did yesterday.
Therefore:
Today's total = best answer until yesterday + l[i]
If We Perform a High-Effort Task Today
We cannot perform any task yesterday.
Therefore:
Today's total = best answer until day i-2 + h[i]
So the recurrence becomes:
dp[i] = max(
dp[i-1] + l[i],
dp[i-2] + h[i]
)
Why dp[i-2] for High Effort?
This is the most important part of the problem.
Suppose we are on day i and want to perform a high-effort task.
The previous day i-1 must have no task.
Therefore, we cannot simply use:
dp[i-1] + h[i]
because dp[i-1] might represent a solution where a task was performed on day i-1.
Instead, we go back to:
dp[i-2]
Then we skip day i-1 and perform the high-effort task on day i.
So:
high = dp[i-2] + h[i]
DP Recurrence
For every day i:
Option 1: Low-Effort Task
low = dp[i-1] + l[i]
Option 2: High-Effort Task
high = dp[i-2] + h[i]
Take the maximum:
dp[i] = max(low, high)
The do nothing option is implicitly covered because the DP value represents the best result achievable up to that point, and the values are non-negative.
Optimizing Space
Normally, we might create an array:
int[] dp = new int[n];
But we don't actually need the entire DP array.
At day i, we only need:
dp[i-1]
dp[i-2]
Therefore, we can maintain only two variables:
prev1 = dp[i-1]
prev2 = dp[i-2]
This reduces the auxiliary space from:
O(n)
to:
O(1)
Java Solution
class Solution {
public int maxTask(int[] h, int[] l) {
int n = h.length;
int prev2 = 0; // dp[i-2]
int prev1 = 0; // dp[i-1]
for (int i = 0; i < n; i++) {
int high = h[i] + prev2;
int low = l[i] + prev1;
int current = Math.max(low, high);
prev2 = prev1;
prev1 = current;
}
return prev1;
}
}
Code Explanation
Step 1: Store the Number of Days
int n = h.length;
Store the number of days.
Step 2: Store Previous DP Results
int prev2 = 0;
int prev1 = 0;
We don't create a complete DP array.
Instead:
prev2 = dp[i-2]
prev1 = dp[i-1]
Initially, both are 0.
Step 3: Process Each Day
for (int i = 0; i < n; i++) {
Process each day one by one.
Step 4: Calculate the High-Effort Option
int high = h[i] + prev2;
If we perform a high-effort task today:
high = h[i] + dp[i-2]
We use prev2 because yesterday must be skipped.
Step 5: Calculate the Low-Effort Option
int low = l[i] + prev1;
If we perform a low-effort task today:
low = l[i] + dp[i-1]
We can use the best result from yesterday.
Step 6: Choose the Better Option
int current = Math.max(low, high);
We choose whichever option produces more tasks.
Step 7: Update the DP Variables
prev2 = prev1;
prev1 = current;
After processing the current day:
old dp[i-1] → dp[i-2]
current → dp[i-1]
This allows us to continue without maintaining a complete DP array.
Step 8: Return the Result
return prev1;
When the loop finishes, prev1 contains the maximum number of tasks that can be completed.
Dry Run
Let's use:
h = [2, 8, 1]
l = [1, 2, 1]
Initially:
prev2 = 0
prev1 = 0
Day 0
High:
high = 2 + 0
= 2
Low:
low = 1 + 0
= 1
Maximum:
current = max(2, 1)
= 2
Update:
prev2 = 0
prev1 = 2
Day 1
High:
high = 8 + prev2
= 8 + 0
= 8
Low:
low = 2 + prev1
= 2 + 2
= 4
Maximum:
current = max(8, 4)
= 8
Update:
prev2 = 2
prev1 = 8
Day 2
High:
high = 1 + 2
= 3
Low:
low = 1 + 8
= 9
Maximum:
current = max(3, 9)
= 9
Final result:
answer = 9
Another Example
Consider:
h = [3, 6, 8, 7, 6]
l = [1, 5, 4, 5, 3]
One optimal strategy is:
Day 0 → High effort = 3
Day 1 → Low effort = 5
Day 2 → Low effort = 4
Day 3 → Low effort = 5
Day 4 → Low effort = 3
Total:
3 + 5 + 4 + 5 + 3 = 20
Therefore:
Output = 20
Why Greedy Doesn't Work
A common mistake is:
Every day, simply choose whichever is larger: h[i] or l[i].
This doesn't work because choosing a high-effort task affects the next day.
For example:
h = [10, 100]
l = [1, 1]
If we choose:
Day 0 → High = 10
we cannot choose a high-effort task on day 1.
However, if we do not perform a task on day 0, we can choose:
Day 1 → High = 100
Therefore, the decision for one day depends on future decisions.
That's why Dynamic Programming is suitable for this problem.
Complexity Analysis
There are n days, and each day is processed exactly once.
Time Complexity
O(n)
Auxiliary Space
Only a few variables are used:
prev1
prev2
current
Therefore:
O(1)
The final complexity is:
Time : O(n)
Space : O(1)
Key Takeaways
Consider the choices available for the current day to derive the DP recurrence.
A low-effort task can be performed regardless of the previous day's activity.
A high-effort task requires the previous day to have no task.
The recurrence is:
dp[i] = max(
dp[i-1] + l[i],
dp[i-2] + h[i]
)
Since only the previous two DP states are required, the solution can be optimized to O(1) auxiliary space.
The overall solution runs in O(n) time.
Summary
The problem can be solved efficiently using Dynamic Programming by considering whether the current day uses a low-effort task or a high-effort task. A low-effort task can build on the result from the previous day, while a high-effort task must use the result from two days earlier because the previous day must remain empty. By maintaining only the previous two DP states, the solution achieves O(n) time complexity and O(1) auxiliary space.