3282. Reach End of Array With Max Score

Problem Description

You are given an integer array nums of length n. Your objective is to start at index 0 and reach index n - 1. The constraint is that you can only jump to indices that are greater than your current index.

The score for a jump from index i to index j is calculated as (j - i) * nums[i].

You need to return the maximum possible total score by the time you reach the last index.

Intuition

To maximize the total score by the time you reach the last index, consider the score formula (j - i) * nums[i]. It indicates that the score is proportional to both the distance jumped (j - i) and the value at the starting index nums[i].

In order to achieve the maximum score, you'd want to maximize the value of nums[i] at every jump. Therefore, you should opt to jump to the next index with a nums value greater than or equal to any previous unvisited index whenever possible. This prevents any potential loss in score by ensuring you continually jump from the maximum value encountered so far.

A greedy approach is suitable here because this dynamic updates of mx (maximum value encountered so far), along with adding mx repeatedly, will naturally calculate the maximum potential score. The problem can be solved by traversing through the array and updating a variable mx to always maintain the highest nums value seen so far. Through each step, accumulate mx to ensure maximum score accumulation.

Learn more about Greedy patterns.

Solution Approach

The solution employs a greedy algorithm to maximize the total score. The central idea is to maintain a running maximum of the nums[i] values encountered as you iterate through the array. This ensures that every jump is made from the maximum value encountered so far, optimizing the score accumulation.

Here's how the solution is implemented:

Initialization: Start by defining two variables: ans to store the accumulated score, initialized to 0, and mx to track the maximum value encountered, also initialized to 0.
Iteration: Traverse the array nums from the first index up to the second-to-last index. It's unnecessary to include the last index since the goal is to reach it, not jump from it.
Maintain Maximum: For each element x in the array during the iteration, update mx to be the maximum of the current mx and x. This step ensures that mx always holds the largest nums[i] encountered from the start up to the current index.
Accumulate Score: Add the value of mx to ans. This step simulates making a "jump" with a score calculated using the maximum value seen so far. Effectively, you're "spending" each step with the optimal nums[i] value you could have seen.
Return Result: Finally, ans contains the maximum possible total score by the time the last index is reached, and it is returned.

The clever update of mx throughout the traversal allows the algorithm to remain efficient and operate in linear time, O(n), making it suitable for large input sizes.

The code snippet implementing this approach is as follows:

class Solution:
    def findMaximumScore(self, nums: List[int]) -> int:
        ans = mx = 0
        for x in nums[:-1]:
            mx = max(mx, x)
            ans += mx
        return ans

This greedy approach ensures that each jump contributes maximally to the total score by relying on the highest nums[i] value encountered thus far.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's consider an example to illustrate the solution approach.

Suppose we have an array nums = [3, 1, 5, 2].

Our goal is to start at index 0 and reach index 3, maximizing the total score.

Initialization: We start with ans = 0 to accumulate the score and mx = 0 to keep track of the maximum nums[i] encountered.
Iteration over the array:
- Index 0 (nums[0] = 3):
  - Update mx, which becomes max(0, 3) = 3.
  - Add mx to ans: ans = 0 + 3 = 3.
- Index 1 (nums[1] = 1):
  - Update mx, which stays max(3, 1) = 3.
  - Add mx to ans: ans = 3 + 3 = 6.
- Index 2 (nums[2] = 5):
  - Update mx, which becomes max(3, 5) = 5.
  - Add mx to ans: ans = 6 + 5 = 11.
Conclusion: We reach the last index, index 3, with a score of 11.

Thus, the maximum possible total score is 11.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findMaximumScore(self, nums: List[int]) -> int:
5        ans = 0  # Initialize the sum of maximums to zero
6        current_max = 0  # Initialize the current maximum element
7
8        # Loop through each element in the list except the last one
9        for num in nums[:-1]:  
10            # Update the current maximum with the current element if it is larger
11            current_max = max(current_max, num)
12            # Add the current maximum to the answer
13            ans += current_max
14      
15        return ans  # Return the final accumulated maximum sum
16

1import java.util.List;
2
3class Solution {
4
5    public long findMaximumScore(List<Integer> nums) {
6        long ans = 0; // Variable to store the accumulated score
7        int maxSoFar = 0; // Variable to track the maximum value seen so far in the list
8
9        // Iterate through the list, stopping before the last element
10        for (int i = 0; i < nums.size() - 1; ++i) {
11            // Update maxSoFar with the maximum of the current element and maxSoFar
12            maxSoFar = Math.max(maxSoFar, nums.get(i));
13            // Add the current maxSoFar to the total score
14            ans += maxSoFar;
15        }
16
17        return ans; // Return the accumulated score
18    }
19}
20

1class Solution {
2public:
3    long long findMaximumScore(std::vector<int>& nums) {
4        long long ans = 0;  // Initialize the answer to 0
5
6        int mx = 0;  // Initialize the maximum value found so far
7        for (int i = 0; i + 1 < nums.size(); ++i) {  // Loop through elements of the vector, except the last one
8            mx = std::max(mx, nums[i]);  // Update the maximum value if the current element is greater
9            ans += mx;  // Add the maximum value to the answer
10        }
11
12        return ans;  // Return the computed maximum score
13    }
14};
15

1function findMaximumScore(nums: number[]): number {
2    // Initialize variables; ans will store the accumulated sum, mx will track the maximum value encountered.
3    let ans: number = 0;
4    let mx: number = 0;
5  
6    // Iterate over the nums array excluding the last element.
7    for (const x of nums.slice(0, -1)) {
8        // Update mx to be the maximum of the current mx or the current element x.
9        mx = Math.max(mx, x);
10        // Add the current mx to the ans.
11        ans += mx;
12    }
13  
14    // Return the accumulated sum as the maximum score.
15    return ans;
16}
17

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the array nums. This is because the code iterates through the nums list once, performing a constant amount of work for each element.

The space complexity is O(1), as the code uses a fixed amount of additional space regardless of the input size, primarily for the variables ans and mx.

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:

Question 1 out of 10

Which algorithm should you use to find a node that is close to the root of the tree?

DFS

BFS

Binary search

Backtracking

I don’t know