2786. Visit Array Positions to Maximize Score
Problem Description
You are provided with an int
array nums
that is 0-indexed and a positive int
x
. The goal is to calculate the maximum total score you can obtain starting at position 0
of the array and moving to any subsequent position. The rules are outlined as follows:
- You can move from your current position
i
to any positionj
such thati < j
. - When you visit position
i
, you earnnums[i]
points added to your score. - If you move between positions
i
andj
andnums[i]
andnums[j]
have different parities (one is odd, the other is even), you losex
points from your score.
You kick off with nums[0]
points, and you have to figure out the maximum score that can be achieved under these conditions.
Intuition
The task is to maximize the score while taking into account that moving between numbers of different parity comes with a penalty of x
points. To do this, we need to use dynamic programming to track the highest scores while considering the parity of the current number.
Here's an outline of the approach:
- Initialize a list
f
with two elements, set to negative infinity[-inf, -inf]
. This list will keep track of the max scores for even and odd indices. - Set the element of
f
corresponding to the parity ofnums[0]
(even or odd) tonums[0]
. This represents the score starting at position0
. - Iterate through the
nums
array starting from index1
. For each valuev
at indexi
:- Calculate the maximum score when staying on the same parity (
f[v & 1] + v
) and when changing parity (f[v & 1 ^ 1] + v - x
). - Update
f[v & 1]
with the highest score from the above step.
- Calculate the maximum score when staying on the same parity (
- After processing all elements, the maximum score will be the maximum element from
f
.
The key intuition in this solution comes from recognizing that at any index i
in the array, you have two scenarios to consider:
- The last score came from an index with the same parity as
i
. In this case, you just add the current value to the previous score since no penalty is incurred. - The last score came from an index with different parity. Here, you add the current value to the previous score from the opposite parity and subtract the penalty
x
.
This process will lead us to the highest possible score, taking into account the penalty for switching parities.
Learn more about Dynamic Programming patterns.
Solution Approach
The implementation uses a dynamic programming approach to compute the maximum score. Here's a step-by-step walkthrough:
-
Firstly, the algorithm initializes a list
f
with two elements,[-inf, -inf]
. This record is to keep track of the two possible states for our score related to parity: even (0
) and odd (1
). In Python,-inf
denotes negative infinity which is a useful placeholder for "not yet computed or improbably low score." -
The first element of
nums
is factored into our initial state. Since we always start at position0
,f[nums[0] & 1]
is set tonums[0]
. The expressionnums[0] & 1
will be0
ifnums[0]
is even, and1
if it is odd, so it determines the index off
that gets updated. -
The algorithm then iterates through elements in
nums
starting from index1
. For each valuev
, it computes the two possible scenarios:- Staying on the same parity (
f[v & 1] + v
), - Switching parity (
f[v & 1 ^ 1] + v - x
). The^
operator is a bitwise XOR, which flips the bit, effectively getting us the other parity.
The update for the score at parity
v & 1
chooses whichever of these two possibilities gives a higher score. This is done by themax
function. - Staying on the same parity (
-
After evaluating all elements in
nums
, the maximum score is the highest value inf
, which can be obtained using Python's built-inmax(f)
function.
The code snippet provided succinctly translates this approach into a Python function as part of a Solution
class:
1class Solution:
2 def maxScore(self, nums: List[int], x: int) -> int:
3 f = [-inf] * 2
4 f[nums[0] & 1] = nums[0]
5 for v in nums[1:]:
6 f[v & 1] = max(f[v & 1] + v, f[v & 1 ^ 1] + v - x)
7 return max(f)
Each iteration effectively represents a choice at every position i
with a value v
from nums
: taking its score as part of the existing parity sequence or starting a new sequence of the opposite parity with an x
penalty. The algorithm dynamically keeps track of the best choice by updating only the score of the relevant parity after each decision. This pattern avoids the need for recursive traversal through all potential positions and parities, significantly reducing the complexity of the problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example:
Suppose we have the array nums = [4, 5, 2, 7, 3]
and the penalty x = 3
.
We initiate the variable f
with two elements [-inf, -inf]
to keep track of the max scores for the even (f[0]
) and odd indices (f[1]
).
f = [-inf, -inf]
Starting at position 0
, nums[0] = 4
, which is even, so we update f[0]
with the value of nums[0]
.
f = [4, -inf]
We move to nums[1] = 5
, which is odd:
- If we stay with odd,
f[1]
would become5
(since-inf + 5
is just5
), but there's a catch: we start from an even index so we must apply the penaltyx
. The new score would be5 - 3 = 2
. - If we switch to even,
f[0] + nums[1]
would be4 + 5 = 9
. We take the max of both, which is9
, so we updatef[1]
. f = [4, 9]
Next, nums[2] = 2
, which is even:
- Staying with even parity,
f[0] + 2 = 4 + 2 = 6
. - Switching to odd,
f[1] + 2 - x = 9 + 2 - 3 = 8
. The higher score is8
, sof[0]
becomes8
. f = [8, 9]
With nums[3] = 7
, which is odd:
- Staying odd,
f[1] + 7 = 9 + 7 = 16
. - Switching to even,
f[0] + 7 - x = 8 + 7 - 3 = 12
. We take the max which is16
and updatef[1]
. f = [8, 16]
Lastly, nums[4] = 3
, which is odd:
- Staying odd,
f[1] + 3 = 16 + 3 = 19
. - Switching to even,
f[0] + 3 - x = 8 + 3 - 3 = 8
. The max is19
, sof[1]
remains19
. f = [8, 19]
The maximum score we can get is max(f)
, which is 19
.
The entire process demonstrates the dynamic programming algorithm's effectiveness in computing the maximum score by considering the penalty for switching between even and odd numbers. Each decision is based on whether to continue the sequence of the current parity or start a new one of the opposite parity with a penalty. The algorithm avoids the need to check each path separately, instead of using a running tally that gets updated in each step, which is considerably more efficient.
Solution Implementation
1from typing import List
2import math
3
4class Solution:
5 def maxScore(self, nums: List[int], x: int) -> int:
6 # Initialize a list with two elements representing negative infinity
7 # The list is used to track the maximum scores for even and odd numbers separately
8 max_scores = [-math.inf, -math.inf]
9
10 # The first number's score is determined based on its parity (even/odd)
11 # and assigned as the initial score for that parity
12 max_scores[nums[0] % 2] = nums[0]
13
14 # Iterate over the remaining numbers starting from the second element
15 for value in nums[1:]:
16 # Determine the parity of the current number, 0 if even, 1 if odd
17 parity = value % 2
18 # Update the score for the current parity
19 # max() is choosing the greater value between continuing the same parity
20 # or switching parity and applying the penalty/subtraction of x
21 max_scores[parity] = max(max_scores[parity] + value, max_scores[parity ^ 1] + value - x)
22
23 # Return the maximum score between the even and odd parities
24 return max(max_scores)
25
1class Solution {
2
3 // Method to calculate the maximum score.
4 public long maxScore(int[] nums, int x) {
5
6 // Array f to store the current maximum score for odd and even indexed numbers.
7 long[] maxScoreForOddEven = new long[2];
8
9 // Initialize both entries with a very small number to simulate negative infinity.
10 Arrays.fill(maxScoreForOddEven, -(1L << 60));
11
12 // The first number decides the initial maximum score for its parity (odd or even).
13 maxScoreForOddEven[nums[0] & 1] = nums[0];
14
15 // Iterate over the array, starting from the second element.
16 for (int i = 1; i < nums.length; ++i) {
17
18 // numParity is 0 for even and 1 for odd.
19 int numParity = nums[i] & 1;
20
21 // Update the maximum score for the current parity (odd or even).
22 maxScoreForOddEven[numParity] = Math.max(
23 maxScoreForOddEven[numParity] + nums[i], // Case when adding the current number to the same parity.
24 maxScoreForOddEven[numParity ^ 1] + nums[i] - x // Case when adding the current number leads to change in parity
25 // with the penalty x.
26 );
27 }
28
29 // Return the maximum score among the two parities.
30 return Math.max(maxScoreForOddEven[0], maxScoreForOddEven[1]);
31 }
32}
33
1#include <vector>
2#include <algorithm> // For max() function
3using namespace std;
4
5class Solution {
6public:
7 long long maxScore(vector<int>& nums, int x) {
8 // Define an infinite value for long long type
9 const long long INF = 1LL << 60;
10
11 // Create a vector to track the maximum scores for even and odd indices
12 vector<long long> maxScores(2, -INF); // Initialized with -INF
13
14 // Initialize the first element of the score according to whether it's even or odd
15 maxScores[nums[0] & 1] = nums[0];
16
17 // Calculate the number of elements
18 int n = nums.size();
19
20 // Loop over the elements starting from the second element
21 for (int i = 1; i < n; ++i) {
22 // Update the max score for the current parity (even/odd index) of the number
23 // This is the maximum of either adding the current number to the existing
24 // score of the same parity, or switching parity and subtracting the penalty x
25 maxScores[nums[i] & 1] = max(
26 maxScores[nums[i] & 1] + nums[i], // Same parity: add current number
27 maxScores[(nums[i] & 1) ^ 1] + nums[i] - x // Opposite parity: switch parity and subtract x
28 );
29 }
30
31 // Return the maximum value of the two max scores
32 return max(maxScores[0], maxScores[1]);
33 }
34};
35
1function maxScore(nums: number[], x: number): number {
2 // Define a very large number to represent "infinity".
3 const INFINITY = 1 << 30;
4 // Initialize an array 'scores' with two elements representing the max scores for even and odd indices.
5 const scores: number[] = Array(2).fill(-INFINITY);
6 // For the first number, update the score based on it being even or odd.
7 scores[nums[0] & 1] = nums[0];
8
9 // Loop through the numbers starting from the second element.
10 for (let i = 1; i < nums.length; ++i) {
11 const isOdd = nums[i] & 1;
12 // Update the score for the current parity (even or odd).
13 // The updated score is the max of the current score for the same parity plus the current number,
14 // or the score for the other parity plus the current number minus x.
15 scores[isOdd] = Math.max(scores[isOdd] + nums[i], scores[isOdd ^ 1] + nums[i] - x);
16 }
17
18 // Return the maximum score between the even and odd indices.
19 return Math.max(scores[0], scores[1]);
20}
21
Time and Space Complexity
The given Python code snippet aims to calculate a certain "maximum score" by iterating through the input list nums
and applying some operations based on the elements' parity (odd or even) and a given integer x
. To analyze the time and space complexity of this code, let's consider n
to be the length of the input list nums
.
Time Complexity
The time complexity of this code is determined by the number of operations performed in the for-loop that iterates through the nums
list:
- The for-loop runs
(n - 1)
times, as it starts from the second element innums
. - Within the loop, a constant number of operations are executed: two bitwise AND operations, four direct accesses by index to the list
f
, up to two max operations, and a few arithmetic operations.
Since these operations inside the loop are all of constant time complexity, the overall time complexity of the loop is O(n - 1)
. Simplifying this, we get:
O(n - 1)
= O(n)
.
Thus, the time complexity of the code is O(n)
.
Space Complexity
As for the space complexity:
- A new list
f
of fixed size 2 is created. This does not depend on the size of the input and is thusO(1)
. - Variable
v
is a single integer that is used to iterate throughnums
, which is alsoO(1)
space. - There are no other data structures or recursive calls that use additional space that scales with the input size.
Therefore, the space complexity of the code is O(1)
.
Without a reference answer provided alongside the code, the analysis is based solely on the provided snippet.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the minimum element can be found in:
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first