Leetcode 2786: Visit Array Positions to Maximize Score
You are given an integer array ’nums’ and a positive integer ‘x’. Starting at index 0, you can move to any position j (where i < j). For each position i that you visit, you get a score of nums[i]. If the parities of nums[i] and nums[j] differ, you lose a score of ‘x’. Your goal is to find the maximum score you can accumulate by visiting positions in the array.
Problem
Approach
Steps
Complexity
Input: You are given an integer array nums and a positive integer x.
Example: Input: nums = [5, 10, 3, 7], x = 4
Constraints:
• 2 <= nums.length <= 10^5
• 1 <= nums[i], x <= 10^6
Output: Return the maximum score you can achieve by visiting positions in the array according to the given rules.
Example: Output: 19
Constraints:
Goal: Maximize the total score by choosing the optimal positions to visit based on the parity conditions.
Steps:
• Initialize the scores for the even and odd cases based on nums[0].
• Iterate through the array, updating the scores based on the parity of nums[i] and the maximum possible score from previous positions.
• Return the maximum score from the even or odd score variable.
Goal: The input array length and the value of x.
Steps:
• nums.length is between 2 and 10^5.
• Each value in nums is between 1 and 10^6.
• x is between 1 and 10^6.
Assumptions:
• The input array nums contains integers and is not empty.
• Input: Input: [5, 10, 3, 7], x = 4
• Explanation: Starting at index 0, we first gain 5 points. Then moving to index 1, we gain 10 but lose 4 points because the parities of 5 (odd) and 10 (even) differ. Then, moving to index 3, we gain 7 but lose another 4 points because the parities of 10 (even) and 7 (odd) differ. The final score is 5 + 10 + 7 - 4 - 4 = 19.
• Input: Input: [2, 4, 6, 8], x = 2
• Explanation: All values are even, so no penalties are incurred. The total score is 2 + 4 + 6 + 8 = 20.
Approach: We will use dynamic programming to track the maximum possible score at each position based on the parity of the current and previous positions.
Observations:
• The problem can be solved by maintaining separate scores for even and odd parities as we iterate through the array.
• I will track the maximum score for both even and odd parities as I move through the array.
Steps:
• Initialize the scores for even and odd parities using nums[0].
• Iterate through the array and update the scores based on the parity comparison of nums[i] with the previous score.
• Return the maximum of the even or odd score after processing the entire array.
Empty Inputs:
• Input: []. Output: 0 (empty array should not be a valid input, but could return 0 if handled).
Large Inputs:
• Input: A large array with 10^5 elements. The solution should work within time limits.
Special Values:
• Input: All numbers are the same. The result will be the sum of all numbers.
Constraints:
• The solution should run efficiently for up to 10^5 elements.
long long maxScore(vector<int>& n, int x) {
long long eve = n[0] - (n[0] % 2 ? x : 0);
long long odd = n[0] - (n[0] % 2 ? 0 : x);
for (int i = 1; i < n.size(); ++i)
if (n[i] % 2) odd = n[i] + max(odd, eve - x);
else eve = n[i] + max(eve, odd - x);
return max(eve, odd);
}
1 : Function Declaration
long long maxScore(vector<int>& n, int x) {
The function `maxScore` is declared, taking a vector `n` of integers and an integer `x` as inputs. It returns a long long value, representing the maximum score that can be achieved.
2 : Variable Initialization
long long eve = n[0] - (n[0] % 2 ? x : 0);
The variable `eve` is initialized to the first element of the array `n`. If the element is odd, it subtracts `x`; if the element is even, no subtraction occurs.
3 : Variable Initialization
long long odd = n[0] - (n[0] % 2 ? 0 : x);
Similarly, the variable `odd` is initialized to the first element of `n`. If the element is even, it subtracts `x`; if the element is odd, no subtraction occurs.
4 : Loop Initialization
for (int i = 1; i < n.size(); ++i)
A for loop is initialized starting from index 1 to iterate through the elements of the vector `n` from the second element onward.
5 : Odd Case Calculation
if (n[i] % 2) odd = n[i] + max(odd, eve - x);
If the current element `n[i]` is odd (i.e., `n[i] % 2` evaluates to true), the `odd` variable is updated. It takes the maximum of the current `odd` value and the `eve` value minus `x`, then adds the current element `n[i]`.
6 : Even Case Calculation
else eve = n[i] + max(eve, odd - x);
If the current element `n[i]` is even, the `eve` variable is updated by adding the maximum of the current `eve` value and the `odd` value minus `x`.
7 : Returning Result
return max(eve, odd);
After the loop finishes, the function returns the maximum of the `eve` and `odd` scores, which represents the highest achievable score after considering all elements.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is linear since we only iterate through the array once.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant since we only need to store two variables for tracking scores.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus