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 <= 103
• 1 <= nums[i] <= 105

Solutions

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

The execution process of the function $\text{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 \text{nums}[j]$, plus the maximum score that can be obtained starting from index $j$, making the total score $(j - i) \times \text{nums}[j] + \text{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 $\text{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.

• 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 = [&](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(dfs, j));
}
return f[i];
};
return dfs(dfs, 0);
}
};

• 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)

• 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);
}