3205. Maximum Array Hopping Score I 🔒

Description

Given an array nums, you have to get the maximum score starting from index 0 and hopping until you reach the last element of the array.

In each hop, you can jump from index i to an index j > i, and you get a score of (j - i) * nums[j].

Return the maximum score you can get.

Example 1:

Input: nums = [1,5,8]

Output: 16

Explanation:

There are two possible ways to reach the last element:

0 -> 1 -> 2 with a score of (1 - 0) * 5 + (2 - 1) * 8 = 13.
0 -> 2 with a score of (2 - 0) * 8 = 16.

Example 2:

Input: nums = [4,5,2,8,9,1,3]

Output: 42

Explanation:

We can do the hopping 0 -> 4 -> 6 with a score of (4 - 0) * 9 + (6 - 4) * 3 = 42.

Constraints:

2 <= nums.length <= 10³
1 <= nums[i] <= 10⁵

Solutions

Solution 1: Memoization Search

Thinking

From index \(0\) we jump right to some \(j\) and score \((j-i)\times\textit{nums}[j]\), maximizing the total. \(n\le 10^3\) forbids enumerating jump sequences exponentially, yet \(O(n^2)\) states fit the limit.

The subproblem depends only on the start \(i\): once we are at \(i\), the best continuation does not depend on how we arrived. Define \(\textit{dfs}(i)\) as the best score from \(i\), take the max of \((j-i)\times\textit{nums}[j]+\textit{dfs}(j)\) over \(j>i\), and memoize.

We design a function \(\textit{dfs}(i)\), which represents the maximum score that can be obtained starting from index \(i\). Therefore, the answer is \(\textit{dfs}(0)\).

The execution process of the function \(\textit{dfs}(i)\) is as follows:

We enumerate the next jump position \(j\). Thus, the score that can be obtained starting from index \(i\) is \((j - i) \times \textit{nums}[j]\), plus the maximum score that can be obtained starting from index \(j\), making the total score \((j - i) \times \textit{nums}[j] + \textit{dfs}(j)\). We enumerate all possible \(j\) and take the maximum score.

To avoid redundant calculations, we use memoization search. We save the calculated value of \(\textit{dfs}(i)\), so it can be directly returned next time.

The time complexity is \(O(n^2)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array.

Python3JavaC++GoTypeScript

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        @cache
        def dfs(i: int) -> int:
            return max(
                [(j - i) * nums[j] + dfs(j) for j in range(i + 1, len(nums))] or [0]
            )

        return dfs(0)

class Solution {
    private Integer[] f;
    private int[] nums;
    private int n;

    public int maxScore(int[] nums) {
        n = nums.length;
        f = new Integer[n];
        this.nums = nums;
        return dfs(0);
    }

    private int dfs(int i) {
        if (f[i] != null) {
            return f[i];
        }
        f[i] = 0;
        for (int j = i + 1; j < n; ++j) {
            f[i] = Math.max(f[i], (j - i) * nums[j] + dfs(j));
        }
        return f[i];
    }
}

class Solution {
public:
    int maxScore(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        auto dfs = [&](this auto&& dfs, int i) -> int {
            if (f[i]) {
                return f[i];
            }
            for (int j = i + 1; j < n; ++j) {
                f[i] = max(f[i], (j - i) * nums[j] + dfs(j));
            }
            return f[i];
        };
        return dfs(0);
    }
};

func maxScore(nums []int) int {
    n := len(nums)
    f := make([]int, n)
    var dfs func(int) int
    dfs = func(i int) int {
        if f[i] > 0 {
            return f[i]
        }
        for j := i + 1; j < n; j++ {
            f[i] = max(f[i], (j-i)*nums[j]+dfs(j))
        }
        return f[i]
    }
    return dfs(0)
}

function maxScore(nums: number[]): number {
    const n = nums.length;
    const f: number[] = Array(n).fill(0);
    const dfs = (i: number): number => {
        if (f[i]) {
            return f[i];
        }
        for (let j = i + 1; j < n; ++j) {
            f[i] = Math.max(f[i], (j - i) * nums[j] + dfs(j));
        }
        return f[i];
    };
    return dfs(0);
}

Solution 2: Dynamic Programming

Thinking

The recurrence in Solution 1 is already optimal; the recursion stack and cache are unnecessary. The same transfer becomes bottom-up: \(f[j]\) is the best score from \(0\) to \(j\), and each \(j\) enumerates predecessors \(i<j\). The time is still \(O(n^2)\), now iterative.

We can transform the memoization search from Solution 1 into dynamic programming.

Define \(f[j]\) as the maximum score that can be obtained starting from index \(0\) and ending at index \(j\). Therefore, the answer is \(f[n - 1]\).

The state transition equation is:

\[ f[j] = \max_{0 \leq i < j} \{ f[i] + (j - i) \times \textit{nums}[j] \} \]

The time complexity is \(O(n^2)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array.

Python3JavaC++GoTypeScript

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        n = len(nums)
        f = [0] * n
        for j in range(1, n):
            for i in range(j):
                f[j] = max(f[j], f[i] + (j - i) * nums[j])
        return f[n - 1]

class Solution {
    public int maxScore(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        for (int j = 1; j < n; ++j) {
            for (int i = 0; i < j; ++i) {
                f[j] = Math.max(f[j], f[i] + (j - i) * nums[j]);
            }
        }
        return f[n - 1];
    }
}

class Solution {
public:
    int maxScore(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        for (int j = 1; j < n; ++j) {
            for (int i = 0; i < j; ++i) {
                f[j] = max(f[j], f[i] + (j - i) * nums[j]);
            }
        }
        return f[n - 1];
    }
};

func maxScore(nums []int) int {
    n := len(nums)
    f := make([]int, n)
    for j := 1; j < n; j++ {
        for i := 0; i < j; i++ {
            f[j] = max(f[j], f[i]+(j-i)*nums[j])
        }
    }
    return f[n-1]
}

function maxScore(nums: number[]): number {
    const n = nums.length;
    const f: number[] = Array(n).fill(0);
    for (let j = 1; j < n; ++j) {
        for (let i = 0; i < j; ++i) {
            f[j] = Math.max(f[j], f[i] + (j - i) * nums[j]);
        }
    }
    return f[n - 1];
}

Solution 3: Monotonic Stack

Thinking

Solution 2 is still quadratic. From \(i\), jumping to a \(j\) that is not the next value no smaller than the current one cannot beat inserting that intermediate hop, so the optimal path only visits the monotone sequence of next-greater indices. A monotonic stack extracts that index list; scoring adjacent hops is then linear.

We observe that for the current position \(i\), we should jump to the next position \(j\) with the maximum value to obtain the maximum score.

Therefore, we traverse the array \(\textit{nums}\), maintaining a stack \(\textit{stk}\) that is monotonically decreasing from the bottom to the top of the stack. For the current position \(i\) being traversed, if the value corresponding to the top element of the stack is less than or equal to \(\textit{nums}[i]\), we continuously pop the top element of the stack until the stack is empty or the value corresponding to the top element of the stack is greater than \(\textit{nums}[i]\), and then push \(i\) into the stack.

Next, we initialize the answer \(\textit{ans}\) and the current position \(i = 0\), traverse the elements in the stack, each time taking out the top element \(j\), updating the answer \(\textit{ans} += \textit{nums}[j] \times (j - i)\), and then updating \(i = j\).

Finally, return the answer \(\textit{ans}\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array.

Python3JavaC++GoTypeScript

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        stk = []
        for i, x in enumerate(nums):
            while stk and nums[stk[-1]] <= x:
                stk.pop()
            stk.append(i)
        ans = i = 0
        for j in stk:
            ans += nums[j] * (j - i)
            i = j
        return ans

class Solution {
    public int maxScore(int[] nums) {
        Deque<Integer> stk = new ArrayDeque<>();
        for (int i = 0; i < nums.length; ++i) {
            while (!stk.isEmpty() && nums[stk.peek()] <= nums[i]) {
                stk.pop();
            }
            stk.push(i);
        }
        int ans = 0, i = 0;
        while (!stk.isEmpty()) {
            int j = stk.pollLast();
            ans += (j - i) * nums[j];
            i = j;
        }
        return ans;
    }
}

class Solution {
public:
    int maxScore(vector<int>& nums) {
        vector<int> stk;
        for (int i = 0; i < nums.size(); ++i) {
            while (stk.size() && nums[stk.back()] <= nums[i]) {
                stk.pop_back();
            }
            stk.push_back(i);
        }
        int ans = 0, i = 0;
        for (int j : stk) {
            ans += (j - i) * nums[j];
            i = j;
        }
        return ans;
    }
};

func maxScore(nums []int) (ans int) {
    stk := []int{}
    for i, x := range nums {
        for len(stk) > 0 && nums[stk[len(stk)-1]] <= x {
            stk = stk[:len(stk)-1]
        }
        stk = append(stk, i)
    }
    i := 0
    for _, j := range stk {
        ans += (j - i) * nums[j]
        i = j
    }
    return
}

function maxScore(nums: number[]): number {
    const stk: number[] = [];
    for (let i = 0; i < nums.length; ++i) {
        while (stk.length && nums[stk.at(-1)!] <= nums[i]) {
            stk.pop();
        }
        stk.push(i);
    }
    let ans = 0;
    let i = 0;
    for (const j of stk) {
        ans += (j - i) * nums[j];
        i = j;
    }
    return ans;
}

3205. Maximum Array Hopping Score I 🔒

Description

Solutions

Solution 1: Memoization Search

Solution 2: Dynamic Programming

Solution 3: Monotonic Stack

Comments