LeetCode 2555. 两个线段获得的最多奖品 C#
原题链接
中等
作者:
hpstory
,
2023-02-06 11:25:54
,
所有人可见
,
阅读 138
C# 代码
public class Solution {
public int MaximizeWin(int[] prizePositions, int k) {
int n = prizePositions.Length;
int result = 0;
// pre[i]表示0 ~ i - 1可以获得最多奖品的区间长度
int[] pre = new int[n + 1];
int j = 0;
for (int i = 0; i < n; i++){
// 非递减 j < i可以省略
while (prizePositions[i] - prizePositions[j] > k){
j++;
}
result = Math.Max(result, i - j + 1 + pre[j]);
pre[i + 1] = Math.Max(pre[i], i - j + 1);
}
return result;
}
}