Visit Array Positions to Maximize Score - Practice Coding Problems

Visit Array Positions to Maximize Score - Problem

You are given a 0-indexed integer array nums and a positive integer x.

You are initially at position 0 in the array and you can visit other positions according to the following rules:

If you are currently in position i, then you can move to any position j such that i < j.
For each position i that you visit, you get a score of nums[i].
If you move from a position i to a position j and the parities of nums[i] and nums[j] differ, then you lose a score of x.

Return the maximum total score you can get.

Note that initially you have nums[0] points.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,3,6,-5], x = 10

› Output: 8

💡 Note: We can visit positions 0 → 2. Score = 2 + 6 - 10 (parity penalty) = -2. Or visit 0 → 1 → 2: 2 + 3 - 10 + 6 - 10 = -9. Best path: 0 → 2 gives 2 + 6 = 8 (no penalty needed if we optimize properly).

Example 2 — All Same Parity

$ Input: nums = [2,4,6,8], x = 3

› Output: 20

💡 Note: All numbers are even, so no parity penalties. Visit all positions: 2 + 4 + 6 + 8 = 20.

Example 3 — High Penalty

$ Input: nums = [1,5], x = 10

› Output: 1

💡 Note: Both numbers are odd. Start at position 0 with score 1. Moving to position 1 would add 5 but cost 0 (same parity), giving total 6. But we start with nums[0] = 1, so visiting just position 0 gives score 1.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁶ ≤ nums[i] ≤ 10⁶
1 ≤ x ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Array

nums = [2,3,6,-5], x = 10 (penalty for parity change)

Track States

Maintain best scores for even/odd endings at each step

Optimal Score

Return maximum of both ending states

Key Takeaway

🎯 Key Insight: Separate tracking of even/odd ending states eliminates the need to explore all paths

Asked in

A Amazon 15 G Google 12 M Microsoft 8

The key insight is to track maximum scores separately for paths ending with even and odd numbers. The optimal approach uses dynamic programming to maintain two states at each position, considering parity penalties only when switching between odd and even values. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(2^n)	O(n)	Try all possible paths from each position recursively
Dynamic Programming	O(n)	O(1)	Track maximum scores for odd and even endings at each position
Memoized Recursion	O(n²)	O(n)	Add memoization to avoid recomputing same subproblems

Brute Force Recursion — Algorithm Steps

Start from position 0
For each position, try all future positions
Calculate score with parity penalty
Return maximum score among all paths

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin at position 0 with nums[0] score

Explore

Try visiting each future position recursively

Calculate

Apply parity penalty and find maximum

Code -

solution.c — C

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

long long dfs(int* nums, int numsSize, int x, int pos, long long currentScore) {
    long long maxScore = currentScore;
    
    for (int nextPos = pos + 1; nextPos < numsSize; nextPos++) {
        long long penalty = 0;
        if (nums[pos] % 2 != nums[nextPos] % 2) {
            penalty = x;
        }
        
        long long newScore = currentScore + nums[nextPos] - penalty;
        long long result = dfs(nums, numsSize, x, nextPos, newScore);
        if (result > maxScore) {
            maxScore = result;
        }
    }
    
    return maxScore;
}

long long solution(int* nums, int numsSize, int x) {
    return dfs(nums, numsSize, x, 0, nums[0]);
}

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

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Each position can choose to visit or skip every future position, leading to exponential combinations

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth can go up to n levels

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

856 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

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler