Max Shifted Pair Score — Problem Statement & Solution Guide

ArraysMediumBasic Traversal

TimeO(n)

SpaceO(1)

Problem Description

You are given an integer array arr of length n. For every pair of indices (i,j) with 0 ≤ i < j < n, define the score of the pair as arr[i] + arr[j] + 2·i – 3·j. Your task is to determine the maximum score over all possible pairs. The input consists of two lines: the first line contains the integer n, and the second line contains n space‑separated integers representing arr. Output a single integer, the maximum score found.

DSA Pattern Breakdown

"Max Shifted Pair Score"

medium

WHY DOES IT MATTER?

The prefix maximum pattern transforms a quadratic pairwise problem into a linear scan, drastically reducing time complexity. It is essential in interview settings because it demonstrates the candidate’s ability to identify independent sub‑problems and apply dynamic programming principles without overcomplicating the solution.

OPTIMIZATION CHALLENGE

The insight that the index coefficients can be absorbed into a single running value (arr[i] + 2·i) is what reduces the complexity from O(n²) to O(n). Without this, you would need to recompute the best i for every j, which is computationally expensive.

REAL-WORLD CONNECTION

Consider a distributed log system where each log entry has a timestamp (index) and a severity score (arr value). To find the most critical pair of events, you can precompute the best severity plus a time‑based weight for earlier logs, then combine it with later logs. This mirrors how real systems pre‑aggregate metrics for efficient querying.

When explaining this to an interviewer, emphasize that you’re turning a pairwise dependency into two independent scans: one for the left side and one for the right side. Highlight that the linearity of the index terms is what makes the decomposition possible.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem asks for the maximum value of the expression arr[i] + arr[j] + 2·i – 3·j over all pairs (i,j) with i < j. A naive double‑loop would evaluate O(n²) pairs, which is infeasible for n up to 10⁶. The key observation is that the expression can be split into a part that depends only on i and a part that depends only on j: (arr[i] + 2·i) + (arr[j] – 3·j). Thus, for each j we only need the maximum of arr[i] + 2·i among all i < j. This reduces the problem to a single pass where we maintain the best prefix value and update the answer in O(1) per element. The algorithm runs in linear time and constant extra space, making it optimal for large inputs.

The underlying algorithmic pattern is a classic “prefix maximum” or “running best” technique, often used in problems where a pairwise expression can be decomposed into independent components. By precomputing the best value for the left side of the pair, we avoid recomputing it for every j, thereby eliminating the quadratic blow‑up. This pattern is especially powerful when the expression contains linear terms in the indices, as it allows us to absorb the index contribution into a single value that can be updated incrementally.

Because the indices appear with different coefficients (2 for i and –3 for j), the decomposition is not symmetric; we must carefully choose which side to precompute. The optimal solution keeps a running maximum of arr[i] + 2·i and, for each j, evaluates the candidate score using this maximum and arr[j] – 3·j. This approach guarantees that every pair is considered exactly once, and the maximum is found without any nested loops.

Interview Questions on This Problem

Q1How would you modify the algorithm if the score formula were arr[i] + arr[j] + 5·i – 2·j instead of 2·i – 3·j?

The same decomposition applies: precompute max(arr[i] + 5·i) for i < j and then add arr[j] – 2·j. The coefficients change the prefix value but the linearity remains, so the algorithm stays O(n).

Q2A fintech platform needs to process a stream of transaction amounts in real time and compute the maximum shifted pair score on the fly. How would you adapt the algorithm for streaming data?

Maintain the running maximum of arr[i] + 2·i as you receive each new element. For each new element arr[j], compute candidate = currentMax + arr[j] – 3·j and update the global maximum. This yields an online O(1) update per element with O(1) additional memory.

Q3During an interview at a high‑growth startup, the interviewer asks: "What if we had to support queries that ask for the maximum score in a subarray [L,R]?" How would you approach this?

Preprocess prefix maxima of arr[i] + 2·i and suffix minima of arr[j] – 3·j. For a query [L,R], the best pair must have i in [L,R-1] and j in [i+1,R]. We can use a segment tree or sparse table to retrieve the maximum prefix value up to R-1 and the maximum suffix value from L+1 to R, then combine them. This yields O(log n) per query after O(n log n) preprocessing.

Examples

Example 1

Input

4
1 2 3 4

Output

Explanation: All pair scores are: (0,1)=0, (0,2)=-2, (0,3)=-4, (1,2)=1, (1,3)=-1, (2,3)=2. The largest value is 2.

Example 2

Input

3
-5 0 10

Output

Explanation: Pair scores: (0,1)=-8, (0,2)=-1, (1,2)=6. The maximum is 6.

Example 3

Input

5
7 -1 4 2 9

Output

Explanation: Computed scores: (0,1)=3, (0,2)=5, (0,3)=0, (0,4)=4, (1,2)=-1, (1,3)=-6, (1,4)=-2, (2,3)=1, (2,4)=5, (3,4)=5. The highest score is 5.

Example 4

Input

2
-1000000000 1000000000

Output

-3

Explanation: Only pair (0,1) gives -1000000000 + 1000000000 + 0 – 3 = -3, which is the maximum.

Constraints

1 <= n <= 100000
-1000000000 <= arr[i] <= 1000000000
The algorithm must run in O(n) time and O(1) additional space.

Optimal Approach & Strategy

Maintain the maximum value of arr[i] + 2·i seen so far while iterating through the array. For each j, compute candidate = currentMax + arr[j] – 3·j and update the global maximum. This runs in O(n) time and O(1) space.

Brute Force Approach

Check every pair (i,j) with i < j, compute arr[i] + arr[j] + 2·i – 3·j, and keep the maximum. This takes O(n²) time and is impractical for large n.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function maxShiftedPairScore(arr) {
    let maxScore = -Infinity;
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            const score = arr[i] + arr[j] + 2 * i - 3 * j;
            maxScore = Math.max(maxScore, score);
        }
    }
    return maxScore;
}

#include <vector>
#include <algorithm>
#include <climits>

class Solution {
public:
    int maxShiftedPairScore(const std::vector<int>& arr) {
        if (arr.size() < 2) return 0;
        int maxIVal = arr[0]; 
        int maxScore = INT_MIN;
        for (size_t j = 1; j < arr.size(); ++j) {
            int currentJVal = arr[j] - 3 * static_cast<int>(j);
            maxScore = std::max(maxScore, maxIVal + currentJVal);
            maxIVal = std::max(maxIVal, arr[j] + 2 * static_cast<int>(j));
        }
        return maxScore;
    }
};

class Solution {
    public int maxShiftedPairScore(int[] arr) {
        int maxScore = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                int score = arr[i] + arr[j] + 2 * i - 3 * j;
                maxScore = Math.max(maxScore, score);
            }
        }
        return maxScore;
    }
}

def max_shifted_pair_score(arr):
    max_score = float('-inf')
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            score = arr[i] + arr[j] + 2 * i - 3 * j
            max_score = max(max_score, score)
    return max_score

function maxShiftedPairScore(arr) {
    let maxScore = -Infinity;
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            const score = arr[i] + arr[j] + 2 * i - 3 * j;
            maxScore = Math.max(maxScore, score);
        }
    }
    return maxScore;
}

Asked in Top Tech Interviews

PaytmMicrosoft

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.

Max Shifted Pair Score Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Arrays

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Max Shifted Pair Score — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor