3205. Maximum Array Hopping Score I 🔒

MediumStackGreedyArrayDynamic ProgrammingMonotonic Stack

Problem 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.

Intuition

The problem requires us to find the maximum score possible by choosing optimal hops across the array nums. The key component is that each hop from index i to j grants a score computed as (j - i) * nums[j].

To devise a solution, we consider using a recursive approach bolstered by the concept of memoization. The idea is to break down the problem using a recursive function dfs(i), which represents the maximum score attainable starting from index i. What this function does is explore all subsequent indices j > i, calculates the potential score upon hopping to j, and recursively determines the best possible outcome from index j onwards. The decision-making process at each step involves choosing the highest cumulative score possible by evaluating every possible destination from the current index. Memoization is crucial as it prevents recalculations by storing previously computed results for each starting index, thus speeding up the overall process.

By initializing our search from index 0 with the help of the recursive dfs function, we effectively explore all hop possibilities through recursion and dynamic programming mechanics, ensuring that the maximum score obtainable from these strategic hops is returned.

Learn more about Stack, Greedy, Dynamic Programming and Monotonic Stack patterns.

Solution Approach

The solution leverages a recursive function combined with memoization to efficiently explore all potential paths through the array nums, aiming to maximize the score from index 0 to any valid endpoint. Here's a detailed breakdown of the approach:

Recursive Function dfs(i):
The function dfs(i) is designed to calculate the maximum score that can be achieved starting from index i.
Exploring Hops:
- For each position i, consider hopping to every possible subsequent index j such that j > i.
- The score for hopping from i to j is calculated as (j - i) * nums[j].
- To determine the best possible outcome from index j, recursively compute dfs(j).
Combining Scores:
For each possible hop from i to j, the total score is the hop score (j - i) * nums[j] plus the maximum score obtainable from j onwards, which is dfs(j). Therefore, evaluate [(j - i) * nums[j] + dfs(j) for j in range(i + 1, len(nums))] to gather all such possibilities.
Finding the Maximum:
Use the max() function to select the highest score achievable from all explored hops starting from i. If there are no valid j indices (when i is at the last element), the list inside the max() will be empty, so provide a default score of zero using or [0] to handle this edge case.
Memoization:
- Apply the @cache decorator to the dfs function to store results of previously computed calls to dfs(i).
- This reduces redundant calculations and speeds up the recursive calls by direct retrieval for previously solved subproblems.
Starting the Process:
The overall maximum score is obtained by calling dfs(0), which triggers the recursive exploration from the first index of the array.

In the code, the key operation is implemented concisely as:

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

This expression neatly combines recursion, dynamic programming through memoization, and combinatorial search over all valid hops to arrive at the optimal maximum score for the given problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider a small example where the array nums = [2, 3, 1, 4].

Step-by-step Execution:

Initial Call to dfs(0):
Start from index 0 with nums[0] = 2.
Exploring Possible Hops from Index 0:
- Hop to index 1 with nums[1] = 3, score = (1 - 0) * 3 = 3.
- Hop to index 2 with nums[2] = 1, score = (2 - 0) * 1 = 2.
- Hop to index 3 with nums[3] = 4, score = (3 - 0) * 4 = 12.
Evaluate Each Hop:
- For Hop to Index 1 (Score = 3):
  - Call dfs(1) to find the best score from index 1.
  - Explore hops from 1:
    - Hop to index 2, score = (2 - 1) * 1 = 1.
    - Hop to index 3, score = (3 - 1) * 4 = 8.
  - Choose the hop to index 3 as it yields a higher score = 8 + 0 = 8.
  - Total score from index 0 via index 1 = 3 + 8 = 11.
- For Hop to Index 2 (Score = 2):
  - Call dfs(2) to find the best score from index 2.
  - Only one hop to index 3, score = (3 - 2) * 4 = 4.
  - Total score = 2 + 4 = 6.
- For Hop to Index 3 (Score = 12):
  - No further hops possible, as it's the last element.
  - Total score remains 12.
Select Maximum Score:
From the possibilities 11 (via index 1), 6 (via index 2), and 12 (directly to index 3), the maximum score is 12.

Hence, the maximum score starting at index 0 and hopping to reach the end is 12.

Solution Implementation

1from typing import List
2from functools import lru_cache
3
4class Solution:
5    def maxScore(self, nums: List[int]) -> int:
6        # Use lru_cache to memoize results of the dfs function to avoid recomputation
7        @lru_cache(None)
8        def dfs(i: int) -> int:
9            # Calculate the maximum score recursively from index i
10            return max(
11                [(j - i) * nums[j] + dfs(j) for j in range(i + 1, len(nums))] or [0]
12            )
13
14        # Start the depth-first search from the first index
15        return dfs(0)
16

1class Solution {
2    private Integer[] memo;  // Memoization array to store results of subproblems
3    private int[] nums;      // Input array of integers
4    private int n;           // Size of the input array
5
6    public int maxScore(int[] nums) {
7        this.n = nums.length;    // Initialize the size of the array
8        this.memo = new Integer[n];  // Initialize memoization array with nulls
9        this.nums = nums;        // Assign input array to the class variable
10        return dfs(0);           // Start depth-first search from the first index
11    }
12
13    private int dfs(int i) {
14        if (memo[i] != null) {   // Check if result for index i is already computed
15            return memo[i];      // Return the cached result
16        }
17        memo[i] = 0;             // Initialize the result for this index
18        // Iterate over all possible choices for segment ending
19        for (int j = i + 1; j < n; ++j) {
20            // Calculate the score and update the maximum score for index i
21            memo[i] = Math.max(memo[i], (j - i) * nums[j] + dfs(j));
22        }
23        return memo[i];          // Return the maximum score for starting index i
24    }
25}
26

1class Solution {
2public:
3    int maxScore(vector<int>& nums) {
4        int n = nums.size();                  // Get the size of the input vector
5        vector<int> f(n, 0);                  // Initialize a memoization vector with zeros
6
7        // Define a recursive lambda function for depth-first search to calculate the max score
8        function<int(function<int(int)>&, int)> dfs = [&](function<int(int)>& dfs, int i) -> int {
9            if (f[i] != 0) {                  // If already calculated, return the stored value
10                return f[i];
11            }
12
13            for (int j = i + 1; j < n; ++j) { // Iterate over all possible elements after index i
14                // Calculate the score for this pair and update f[i] if it's the maximum found
15                f[i] = max(f[i], (j - i) * nums[j] + dfs(dfs, j));
16            }
17
18            return f[i];                      // Return the maximum score attainable from index i
19        };
20
21        // Call the dfs function starting from index 0 and return the result
22        return dfs(dfs, 0);
23    }
24};
25

1// Function to calculate the maximum score one can achieve from a given array of numbers
2function maxScore(nums: number[]): number {
3    // Get the length of the input array
4    const n = nums.length;
5  
6    // Initialize an array 'f' to store intermediate results for the dynamic programming approach
7    // Fill it with zeros, indicating that no subproblem has been solved yet
8    const f: number[] = Array(n).fill(0);
9  
10    // Helper function using depth-first search with memoization to calculate the maximum score
11    const dfs = (i: number): number => {
12        // If the result for index 'i' is already calculated, return it to avoid redundant calculations
13        if (f[i]) {
14            return f[i];
15        }
16      
17        // Iterate from the next index to the end of the array
18        for (let j = i + 1; j < n; ++j) {
19            // Calculate the score by selecting an interval from 'i' to 'j'
20            // Update the maximum score for the current index 'i' in the 'f' array
21            f[i] = Math.max(f[i], (j - i) * nums[j] + dfs(j));
22        }
23      
24        // Return the calculated result for the current index
25        return f[i];
26    };
27  
28    // Start the DFS from the first index of the array to find the maximum score
29    return dfs(0);
30}
31

Time and Space Complexity

The time complexity of the code is O(n^2). This is because for each starting index i, the code iterates through the remaining elements in the list nums, resulting in a quadratic number of operations relative to the list size.

The space complexity of the code is O(n). This is primarily due to the use of recursion and memoization (@cache), which will store a result for each starting index i once calculated, up to n entries.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: