High Effort vs Low Effort

Time: O(n)

Space: O(n)

Problem Overview

Each day you may rest, do a low-effort task, or do a high-effort task.

Intuition

Each day you may rest, do a low-effort task, or do a high-effort task. High effort is allowed only when the previous day was rest. Maximize total points over n days by remembering, for every day, the best future total after ending that day in rest, low, or high.

Algorithm

1dp[i][0] = best from day i onward if you rest on day i.
2dp[i][1] = best if you take low[i] on day i; dp[i][2] = best if you take high[i].
3Base on day n-1: rest = 0, low = low[n-1], high = high[n-1].
4For i = n-2..0: rest takes max of all next states; low/high take low[i]/high[i] plus max of next rest or low (next high is illegal).
5Answer is max(dp[0][0], dp[0][1], dp[0][2]).

Example Walkthrough

Input: high = [3, 6, 8], low = [2, 3, 4]

1. Day 2 base: rest 0, low 4, high 8.
2. Day 1: high 6 + max(0,4) = 10; low 3 + max(0,4) = 7; rest 8.
3. Day 0: high 3 + max(rest,low next) = 3+8 = 11; other options are not better.

Output: 11

Common Pitfalls

• High needs a rest day immediately before it - after low or high, the next day cannot be high.
• Rest is useful because it unlocks high the following day.
• Fill from the end; each state only depends on day i+1.
• Space can roll to O(1) with three previous variables if desired.

High Effort vs Low Effort.java

Java

// Approach: Each day choose rest, low effort, or high effort. High is allowed
// only when the previous day was rest. dp[i][0/1/2] = best total from day i onward
// ending that day in rest / low / high. Fill from the last day backward and take
// the max of the three states on day 0.
// Time: O(n) Space: O(n)
class Solution {

    public int maxTask(int[] high, int[] low) {
        int n = high.length;
        int dp[][] = new int[n][3];
        // Last day
        dp[n - 1][0] = 0;          // No task
        dp[n - 1][1] = low[n - 1]; // Low task
        dp[n - 1][2] = high[n - 1];// High task

        // Remaining days
        for (int i = n - 2; i >= 0; i--) {
            // Do no task today
            dp[i][0] = Math.max(
                    dp[i + 1][0],
                    Math.max(dp[i + 1][1], dp[i + 1][2])
            );
            // Do low task today
            // Tomorrow cannot do high task
            dp[i][1] = low[i] + Math.max(
                    dp[i + 1][0],
                    dp[i + 1][1]
            );
            // Do high task today
            // Tomorrow cannot do high task
            dp[i][2] = high[i] + Math.max(
                    dp[i + 1][0],
                    dp[i + 1][1]
            );
        }

        return Math.max(
                dp[0][0],
                Math.max(dp[0][1], dp[0][2])
        );
    }
}

Was this solution helpful?