Reach End of Array With Max Score

Reach End of Array With Max Score - Problem

Array Greedy Medium

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

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

Return the maximum possible total score by the time you reach the last index.

Input & Output

Example 1 — Basic Case

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

› Output: 7

💡 Note: Jump from index 0 to 2 (score = 2×1 = 2), then from index 2 to 3 (score = 1×2 = 2). Total = 4. But optimal is 0→2→3: (2×1) + (1×2) = 4, or 0→1→3: (1×1) + (2×3) = 7

Example 2 — Two Elements

$ Input: nums = [3,4]

› Output: 3

💡 Note: Only one jump possible from index 0 to 1: score = (1-0) × 3 = 3

Example 3 — Decreasing Array

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

› Output: 10

💡 Note: Best strategy is to jump directly from 0 to 2: score = (2-0) × 5 = 10

Constraints

2 ≤ nums.length ≤ 10⁵
-10⁶ ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that to maximize score, we should make long jumps from positions with high values. The greedy approach finds the maximum value position and uses it strategically. Best approach is Greedy with Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Maximum Value	O(n)	O(1)	Always jump from the position with maximum value to the end
Brute Force Recursion	O(2ⁿ)	O(n)	Try all possible jump sequences recursively

Greedy Maximum Value — Algorithm Steps

Scan array to find position with maximum value
Jump from start to max position
Jump from max position to end
Calculate total score

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Max Value

Scan array to find position with highest value

Strategic Jump

Jump from start to max position, then to end

Calculate Score

Sum scores from both jumps

Code -

solution.c — C

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

long long solution(int* nums, int n) {
    if (n == 1) return 0;
    if (n == 2) return nums[0];
    
    // Find the position with maximum value
    int maxVal = nums[0];
    int maxPos = 0;
    for (int i = 1; i < n - 1; i++) {  // Don't consider last position
        if (nums[i] > maxVal) {
            maxVal = nums[i];
            maxPos = i;
        }
    }
    
    // Greedy strategy: jump to max position, then to end
    if (maxPos == 0) {
        // If start has max value, jump directly to end
        return (long long)(n - 1) * nums[0];
    } else {
        // Jump to max position, then to end
        long long score1 = (long long)maxPos * nums[0];  // 0 to max_pos
        long long score2 = (long long)(n - 1 - maxPos) * nums[maxPos];  // max_pos to end
        return score1 + score2;
    }
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%lld\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to find maximum value position

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

850 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

Greedy Maximum Value — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler