Maximum Position-Adjusted Gain — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Iterating arrays and tracking min/max
O(n)O(1)Problem Description
You are provided with an integer array nums of length n. Your task is to determine the maximum possible value of the expression nums[j] - nums[i] - (j - i) for any pair of indices (i, j) satisfying 0 <= i < j < n. This expression represents the net gain from moving from index i to index j, where the gain is the difference in values at those indices, penalized by the distance between them. If no valid pair exists (i.e., n < 2), return -1.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximum Position-Adjusted Gain"
WHY DOES IT MATTER?
This pattern—transforming a two‑index expression into a difference of single‑index functions—turns an O(n²) brute force into a linear scan, a technique that appears in stock‑profit, temperature‑rise, and other “max‑difference with constraint” problems.
OPTIMIZATION CHALLENGE
The key insight is algebraic rearrangement: isolate the j‑dependent part (nums[j]‑j) and the i‑dependent part (nums[i]‑i). This decouples the indices and allows a running minimum to capture the optimal i for any future j.
REAL-WORLD CONNECTION
Imagine a delivery robot that earns revenue equal to the value difference between two locations but loses energy proportional to the distance traveled. By pre‑computing the best “starting profit” (value‑minus‑distance) seen so far, the robot can instantly decide the most profitable drop‑off point without re‑evaluating every prior location.
During an interview, write the rearranged formula on the whiteboard first; it signals to the interviewer that you’re looking for a prefix‑min/max pattern rather than jumping straight into code.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The expression nums[j] - nums[i] - (j‑i) can be rearranged as (nums[j] - j) - (nums[i] - i). This transformation reveals that the problem is essentially a maximum difference query where the left term depends only on i and the right term only on j. A naive double loop would evaluate every pair (i, j) in O(n²) time, which quickly becomes infeasible for n up to 10⁵ or larger because the number of pairs grows quadratically. By scanning the array once while maintaining the smallest value of (nums[i] - i) seen so far, we can compute the best possible gain for each j in constant time, yielding an O(n) linear solution. This technique belongs to the broader class of prefix‑minimum/maximum optimizations that turn pairwise comparisons into single‑pass scans, a cornerstone of many array‑based interview problems.
Interview Questions on This Problem
Q1How would you modify the solution if the penalty term were a quadratic distance, i.e., maximize nums[j] - nums[i] - (j‑i)²?
The quadratic term destroys the simple linear decomposition, so we cannot use a constant‑time prefix minimum. The typical approach is to use a monotonic stack or convex hull trick to maintain candidate lines representing ‑(j‑i)² + constant, achieving O(n log n) or O(n) depending on constraints.
Q2Can the same linear‑time strategy be applied when the array is streamed and you cannot store the entire list?
Yes. Since the algorithm only needs the current value (nums[j] - j) and the minimum (nums[i] - i) seen so far, it works with O(1) extra memory and can process the stream element by element without retaining the full array.
Q3Explain why keeping the maximum of (nums[i] + i) instead of the minimum of (nums[i] - i) does not solve the original problem.
The original expression subtracts the distance (j‑i), so after rearrangement the left side is (nums[i] - i). Using (nums[i] + i) would correspond to a different objective (e.g., maximizing (nums[j] + j) - (nums[i] + i)), which does not reflect the required penalty and would produce incorrect results.
Examples
Input
nums = [1, 5, 3, 8, 2]
Output
4
Explanation: Evaluate all valid pairs (i, j): - (0,1): 5 - 1 - 1 = 3 - (0,2): 3 - 1 - 2 = 0 - (0,3): 8 - 1 - 3 = 4 - (0,4): 2 - 1 - 4 = -3 - (1,2): 3 - 5 - 1 = -3 - (1,3): 8 - 5 - 2 = 1 - (1,4): 2 - 5 - 3 = -6 - (2,3): 8 - 3 - 1 = 4 - (2,4): 2 - 3 - 2 = -3 - (3,4): 2 - 8 - 1 = -7 The maximum value is 4, achieved by pairs (0,3) and (2,3).
Input
nums = [10, 9, 8, 7, 6]
Output
-1
Explanation: Evaluate all valid pairs (i, j): - (0,1): 9 - 10 - 1 = -2 - (0,2): 8 - 10 - 2 = -4 - (0,3): 7 - 10 - 3 = -6 - (0,4): 6 - 10 - 4 = -8 - (1,2): 8 - 9 - 1 = -2 - (1,3): 7 - 9 - 2 = -4 - (1,4): 6 - 9 - 3 = -6 - (2,3): 7 - 8 - 1 = -2 - (2,4): 6 - 8 - 2 = -4 - (3,4): 6 - 7 - 1 = -2 The maximum value is -2, but since the problem asks for the maximum and all values are negative, the answer is -2. However, if the problem implies returning -1 only when n<2, then -2 is correct. Let's re-read: 'If no valid pair exists (i.e., n < 2), return -1'. Here n=5, so we return the max value, which is -2.
Input
nums = [5, 5, 5, 5]
Output
-1
Explanation: Evaluate all valid pairs (i, j): - (0,1): 5 - 5 - 1 = -1 - (0,2): 5 - 5 - 2 = -2 - (0,3): 5 - 5 - 3 = -3 - (1,2): 5 - 5 - 1 = -1 - (1,3): 5 - 5 - 2 = -2 - (2,3): 5 - 5 - 1 = -1 The maximum value is -1.
Input
nums = [1, 2, 3, 4, 5]
Output
0
Explanation: Evaluate all valid pairs (i, j): - (0,1): 2 - 1 - 1 = 0 - (0,2): 3 - 1 - 2 = 0 - (0,3): 4 - 1 - 3 = 0 - (0,4): 5 - 1 - 4 = 0 - (1,2): 3 - 2 - 1 = 0 - (1,3): 4 - 2 - 2 = 0 - (1,4): 5 - 2 - 3 = 0 - (2,3): 4 - 3 - 1 = 0 - (2,4): 5 - 3 - 2 = 0 - (3,4): 5 - 4 - 1 = 0 The maximum value is 0.
Constraints
- 2 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Optimal Approach & Strategy
Rewrite the expression to (nums[j] - j) - (nums[i] - i), keep a running minimum of (nums[i] - i) while scanning, and for each j compute the candidate gain in O(1). The overall algorithm is a single linear pass.
Brute Force Approach
Iterate over every possible pair (i, j) with i < j, compute nums[j] - nums[i] - (j - i), and keep the maximum. This requires two nested loops and runs in O(n²) time.
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.