Maximum Position-Adjusted Gain — Problem Statement & Solution Guide
Problem Description
You are given an integer array nums. Find the maximum value of the expression: nums[j] - nums[i] - (j - i) over all pairs of indices (i, j) such that `0 <= i < j < nums.length.
Examples
Input
[10, 1, 2, 4, 7, 7, -6]
Output
-1
Explanation: Step-by-step: We initialize two pointers, i and j, to the start of the array. We also initialize the minimum value, min_val, to the first element of the array. We then iterate through the array with j, updating min_val whenever we find a smaller value. We keep track of the maximum value of nums[j] - nums[i] - (j - i) as we iterate. For the given input, we find that the maximum value is -1.
Input
[1, 2, 3, 4, 5]
Output
0
Explanation: Step-by-step: We initialize two pointers, i and j, to the start of the array. We also initialize the minimum value, min_val, to the first element of the array. We then iterate through the array with j, updating min_val whenever we find a smaller value. We keep track of the maximum value of nums[j] - nums[i] - (j - i) as we iterate. For the given input, we find that the maximum value is 0.
Constraints
- 2 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
Optimal Approach & Strategy
By rewriting the expression as (nums[j] - j) - (nums[i] - i), we can solve it in a single pass. As we iterate through the array with pointer j, we track the minimum value of (nums[i] - i) seen so far (where i < j) and calculate the difference to find the maximum possible gain in O(N) time and O(1) space.
Brute Force Approach
The brute-force approach involves checking every possible pair of indices (i, j) with 0 <= i < j < nums.length. For each pair, we calculate the given expression and keep track of the maximum value. This takes O(N^2) time because of the nested loop.
Verified Code Solutions
function maxPositionAdjustedGain(nums) {
let maxGain = -Infinity;
let minVal = Infinity;
let minIndex = 0;
for (let j = 1; j < nums.length; j++) {
const currentVal = nums[j] - nums[minIndex] - (j - minIndex);
maxGain = Math.max(maxGain, currentVal);
if (nums[j] < minVal) {
minVal = nums[j];
minIndex = j;
}
}
return maxGain;
}#include <vector>
#include <algorithm>
#include <climits>
class Solution {
public:
int maxPositionAdjustedGain(const std::vector<int>& nums) {
if (nums.empty()) return 0;
int maxGain = INT_MIN;
int minVal = nums[0] - 0;
for (size_t j = 1; j < nums.size(); ++j) {
int currentVal = nums[j] - static_cast<int>(j);
maxGain = std::max(maxGain, currentVal - minVal);
minVal = std::min(minVal, currentVal);
}
return maxGain;
}
};class Solution {
public int solution(int[] nums) {
int max_val = Integer.MIN_VALUE;
int min_val = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
max_val = Math.max(max_val, nums[j] - nums[i] - (j - i));
min_val = Math.min(min_val, nums[i]);
}
}
return max_val;
}
}def solution(nums):
max_val = float('-inf')
min_val = float('inf')
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
max_val = max(max_val, nums[j] - nums[i] - (j - i))
min_val = min(min_val, nums[i])
return max_valfunction maxPositionAdjustedGain(nums) {
let maxGain = -Infinity;
let minVal = Infinity;
let minIndex = 0;
for (let j = 1; j < nums.length; j++) {
const currentVal = nums[j] - nums[minIndex] - (j - minIndex);
maxGain = Math.max(maxGain, currentVal);
if (nums[j] < minVal) {
minVal = nums[j];
minIndex = j;
}
}
return maxGain;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.