Skip to content

3979. Maximum Valid Pair Sum

Description

You are given an integer array nums of length n and an integer k.

A pair of indices (i, j) is called valid if:

  • 0 <= i < j < n
  • j - i >= k

Return the maximum value of nums[i] + nums[j] among all valid pairs.

Β 

Example 1:

Input: nums = [1,3,5,2,8], k = 2

Output: 13

Explanation:

The valid pairs are:

  • (0, 2): nums[0] + nums[2] = 6
  • (0, 3): nums[0] + nums[3] = 3
  • (0, 4): nums[0] + nums[4] = 9
  • (1, 3): nums[1] + nums[3] = 5
  • (1, 4): nums[1] + nums[4] = 11
  • (2, 4): nums[2] + nums[4] = 13

Thus, the answer is 13.​​​​​​​

Example 2:

Input: nums = [5,1,9], k = 1

Output: 14

Explanation:

  • Since k = 1, every pair is valid.
  • The maximum value is obtained from a pair (0, 2)​​​​​​​, which is nums[0] + nums[2] = 5 + 9 = 14.
  • Thus, the answer is 14.

Β 

Constraints:

  • 2 <= n == nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= n - 1

Solutions

Solution 1: Sliding Window

For a valid pair \((i, j)\), we require \(j - i \geq k\), i.e., \(i \leq j - k\). We enumerate the right endpoint \(j\) starting from \(k\). For each \(j\), the maximum left endpoint is \(j - k\). We maintain the maximum value \(x\) of \(\textit{nums}[i]\) in the range \([0, j - k]\), and update the answer with \(x + \textit{nums}[j]\).

The time complexity is \(O(n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array \(\textit{nums}\).

1
2
3
4
5
6
7
8
class Solution:
    def maxValidPairSum(self, nums: list[int], k: int) -> int:
        ans = x = 0
        for j in range(k, len(nums)):
            y = nums[j]
            x = max(x, nums[j - k])
            ans = max(ans, x + y)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int maxValidPairSum(int[] nums, int k) {
        int ans = 0;
        int x = 0;
        for (int j = k; j < nums.length; ++j) {
            int y = nums[j];
            x = Math.max(x, nums[j - k]);
            ans = Math.max(ans, x + y);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int maxValidPairSum(vector<int>& nums, int k) {
        int ans = 0;
        int x = 0;
        for (int j = k; j < nums.size(); ++j) {
            int y = nums[j];
            x = max(x, nums[j - k]);
            ans = max(ans, x + y);
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
func maxValidPairSum(nums []int, k int) int {
    var ans, x int
    for j := k; j < len(nums); j++ {
        y := nums[j]
        x = max(x, nums[j-k])
        ans = max(ans, x+y)
    }
    return ans
}

1
2
3
4
5
6
7
8
9
function maxValidPairSum(nums: number[], k: number): number {
    let [ans, x] = [0, 0];
    for (let j = k; j < nums.length; ++j) {
        const y = nums[j];
        x = Math.max(x, nums[j - k]);
        ans = Math.max(ans, x + y);
    }
    return ans;
}

Comments