We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Array Hopping Score I

Number: 3513

Difficulty: Medium

Paid? Yes

Companies: Zluri

Problem Description

Given an array of integers nums, you start at index 0 and need to reach the last element. In each hop from index i to any index j (j > i), you earn a score calculated as (j - i) * nums[j]. The goal is to determine the maximum score you can accumulate by hopping from the beginning to the end of the array.

Key Insights

  • Use dynamic programming where dp[j] represents the maximum score achievable upon reaching index j.
  • Update dp[j] by considering all possible previous indices i and choosing the maximum among dp[i] + (j - i) * nums[j].
  • The problem constraints (nums.length up to 10^3) allow an O(n^2) solution.
  • Although there are hints of using stacks or greedy methods, the straightforward dynamic programming approach is sufficient.

Space and Time Complexity

Time Complexity: O(n^2) where n is the number of elements in nums. Space Complexity: O(n) for the dp array.

Solution

The solution uses a dynamic programming approach. We create an array dp of size n, where dp[i] holds the maximum score that can be obtained when reaching index i. We initialize dp[0] = 0 because no score is accumulated at the starting index. Then for each index j from 1 to n-1, we iterate through all indices i less than j, updating dp[j] to max(dp[j], dp[i] + (j - i) * nums[j]). Finally, dp[n-1] is returned as the maximum score. The major insight is iteratively building up the maximum score assuming every possible hop from earlier indices.

Code Solutions

# Function to compute Maximum Array Hopping Score I
def max_hopping_score(nums):
    n = len(nums)
    # dp[i] will store the maximum score achievable reaching index i
    dp = [float('-inf')] * n
    dp[0] = 0  # Starting at index 0, score is 0
    
    # For every index j, compute the best achievable score
    for j in range(1, n):
        for i in range(j):
            # Update dp[j] with the best score from any index i reaching j
            dp[j] = max(dp[j], dp[i] + (j - i) * nums[j])
    
    return dp[n - 1]

# Example usage:
nums = [4,5,2,8,9,1,3]
print(max_hopping_score(nums))  # Expected output: 42
← Back to All Questions