Cache for a linear solution

We don't want to do an N^2 solution here since N=10^5. Since the numbers are all positive, cache the max number from nums.Length-1..j, and use this cached value for a linear computation of the solution. Code is down below, cheers, ACC.

Maximum Valid Pair Sum - LeetCode

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

public class Solution {
    public int MaxValidPairSum(int[] nums, int k)
    {
        int[] maxAt = new int[nums.Length];

        maxAt[maxAt.Length - 1] = nums[nums.Length - 1];
        for (int i = nums.Length - 2; i >= 0; i--)
            maxAt[i] = Math.Max(nums[i], maxAt[i + 1]);

        int retVal = 0;
        for (int i = 0; i < nums.Length - k; i++)
            retVal = Math.Max(retVal, nums[i] + maxAt[i + k]);

        return retVal;
    }
}