Maximum Array Hopping Score I - Practice Coding Problems

Maximum Array Hopping Score I - Problem

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.

Input & Output

Example 1 — Basic Hopping

$ Input: nums = [1,5,3,9,2]

› Output: 29

💡 Note: Optimal path: 0→3→4. Score = (3-0)*9 + (4-3)*2 = 27 + 2 = 29

Example 2 — Minimum Array

$ Input: nums = [5,2]

› Output: 2

💡 Note: Only one jump possible: 0→1. Score = (1-0)*2 = 2

Example 3 — Sequential Jumps

$ Input: nums = [1,2,3,4]

› Output: 12

💡 Note: Best path: 0→3. Score = (3-0)*4 = 12. Better than 0→1→2→3 which gives 8

Constraints

2 ≤ nums.length ≤ 1000
-10³ ≤ nums[i] ≤ 10³
You must start from index 0 and reach the last index

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,5,3,9,2] with indices 0,1,2,3,4

Scoring

Each jump from i to j scores (j-i) × nums[j]

Optimal Path

Path 0→3→4 gives maximum score of 29

Key Takeaway

🎯 Key Insight: The score formula (distance × value) makes it profitable to jump far to high-value elements rather than taking many small jumps

Asked in

a Amazon 15 M Microsoft 12 G Google 8 f Meta 5

The key insight is that the score formula (j-i) × nums[j] rewards both distance and value, making it profitable to jump far to high-value elements. The best approach uses Dynamic Programming to build the optimal solution from the end backwards. Time: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Bottom-Up Dynamic Programming	O(n²)	O(n)	Build solution iteratively from the end backwards
Brute Force Recursion	O(2ⁿ)	O(n)	Try all possible jumping paths recursively
Dynamic Programming (Memoization)	O(n²)	O(n)	Cache recursive results to avoid recomputation

Bottom-Up Dynamic Programming — Algorithm Steps

Create DP array where dp[i] = max score from position i
Start from last position (score = 0)
For each position, try all jumps forward
dp[i] = max of all (j-i)*nums[j] + dp[j]

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with dp[last] = 0

Fill Table

For each position, compute max score from all possible jumps

Result

dp[0] contains the answer

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    int* dp = (int*)calloc(numsSize, sizeof(int));
    
    // Work backwards from second last position
    for (int i = numsSize - 2; i >= 0; i--) {
        int maxScore = 0;
        for (int j = i + 1; j < numsSize; j++) {
            int score = (j - i) * nums[j] + dp[j];
            if (score > maxScore) {
                maxScore = score;
            }
        }
        dp[i] = maxScore;
    }
    
    int result = dp[0];
    free(dp);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[100];
    int numsSize = 0;
    
    char* ptr = strchr(line, '[');
    ptr++;
    char* token = strtok(ptr, ",]");
    
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops: outer loop n positions, inner loop up to n jumps per position

⚠ Quadratic Growth

Space Complexity

O(n)

DP array stores maximum score for each position

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bottom-Up Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler