14.32 Retrieve Optimal Computation

14.32.1 Problem Metadata

14.32.2 Description

You are given an array taste where each entry represents how tasty a chocolate bar is if eaten on day 1. Eating a bar on day d multiplies its taste by d. Each day you may eat exactly one bar from either end of the array. Compute the maximum total taste.

14.32.3 Examples

Input: taste = [1,2,3,4]
Output: 30
Explanation: Eat 1,2,3,4 from left to right for 1*1 + 2*2 + 3*3 + 4*4.

14.32.4 Constraints

  • 1 <= taste.length <= 200
  • 1 <= taste[i] <= 10^3

14.32.5 Solution - Memoized Recursion

14.32.5.1 Walkthrough

When only the subarray taste[i..j] remains, the current day is day = n - (j - i) (since n - (remaining length - 1)). We may take either the left or right value. The optimal result is therefore:

max(day * taste[i] + solve(i+1, j, day+1),
    day * taste[j] + solve(i, j-1, day+1))

Caching the (i, j) results avoids recomputation and yields O(n?) states.

14.32.5.2 Analysis

  • Time Complexity: O(n?)
  • Space Complexity: O(n?) for memoization

14.32.5.3 Implementation Steps

  1. Define dfs(i, j) returning the best score for subarray [i, j].
  2. The current day equals n - (j - i).
  3. Recursively compute both choices (left/right), memoize the maximum, and return it.
  4. Start with dfs(0, n-1).

14.32.5.4 Code - Java

public int maxTaste(int[] taste) {
    int n = taste.length;
    Integer[][] memo = new Integer[n][n];
    return dfs(taste, 0, n - 1, memo);
}

private int dfs(int[] taste, int left, int right, Integer[][] memo) {
    if (memo[left][right] != null) {
        return memo[left][right];
    }

    int day = taste.length - (right - left);
    if (left == right) {
        return day * taste[left];
    }

    int pickLeft = day * taste[left] + dfs(taste, left + 1, right, memo);
    int pickRight = day * taste[right] + dfs(taste, left, right - 1, memo);
    return memo[left][right] = Math.max(pickLeft, pickRight);
}