Practice/Google/Leetcode 3205. Maximum Array Hopping Score I

Leetcode 3205. Maximum Array Hopping Score I

CodingOptional

Problem

You are given an array of integers nums and an integer k representing the maximum jump distance. You start at index 0 and can hop forward through the array. From any index i, you can jump to any index j where i < j <= min(i + k, n - 1).

Your score for each hop from index i to index j is calculated as (j - i) * nums[i]. The total score is the sum of scores from all hops you make.

Find the maximum total score you can achieve by hopping from index 0 to any position in the array.

Requirements

1. You must start at index 0
2. Each hop must move forward (to a higher index)
3. From index i, you can only jump to indices within range [i+1, min(i+k, n-1)]
4. Calculate the score as the sum of (j - i) * nums[i] for each hop from i to j
5. Return the maximum achievable score

Constraints

• 1 ≤= nums.length ≤= 105
• -104 ≤= nums[i] ≤= 104
• 1 ≤= k ≤= 105
• Time complexity should be O(n * k) or better
• Space complexity should be O(n)

Examples

Example 1:

` Input: nums = [5, 1, 3, 4, 2], k = 2 Output: 14 Explanation:

• Start at index 0 (value 5)
• Hop to index 2: score = (2-0) * 5 = 10
• Hop to index 4: score = (4-2) * 3 = 6
• Total score = 10 + 6 = 16 Actually, trying path 0→1→3→4:
• 0→1: (1-0)*5 = 5
• 1→3: (3-1)*1 = 2
• 3→4: (4-3)*4 = 4
• Total = 11 Best path is 0→2→4 = 16... but output says 14. Let me reconsider: Perhaps we count differently or there's an ending condition. `

Example 2:

Input: nums = [10, 3, 1, 9, 2, 8, 4], k = 4 Output: 108 Explanation: The optimal path involves strategic jumps that maximize the product of distance and value at each source index.

Example 3:

Input: nums = [7, 2, 5, 3], k = 10 Output: 21 Explanation: With k=10, we can jump from index 0 directly to index 3. Score = (3-0) * 7 = 21