Maximum Distinct Subarray Sum
MediumSliding Window · NVIDIA
Given an array of positive integers nums and an integer k, consider every contiguous subarray of length exactly k. A subarray is valid if no value appears in it more than once.
Return the largest sum of any valid subarray. If there is no valid subarray, return 0.
Example 1
- Input:
- nums = [4, 2, 7, 7, 3, 5, 1], k = 3
- Output:
- 15
- Explanation
- Windows
[4,2,7](sum 13),[7,3,5](15) and[3,5,1](9) are valid.[2,7,7]and[7,7,3]repeat7, so they do not count even though[7,7,3]sums to 17. The answer is15.
Example 2
- Input:
- nums = [6, 1, 6], k = 3
- Output:
- 0
- Explanation
- The only window of length 3 contains
6twice, so there is no valid window and the answer is0.
Example 3
- Input:
- nums = [3, 9, 9, 2], k = 1
- Output:
- 9
- Explanation
- Every single element is a valid window, so the answer is the largest value,
9.
Constraints
- 1 ≤ k ≤ nums.length ≤ 105
- 1 ≤ nums[i] ≤ 105