1
已解决
初级光能
题目描述 Description
贝蒙喜欢闪闪发光的东西，于是有在空闲时间里挖钻石的爱好。她收集了N颗不同大小的钻石（N≤50000），她想在两个漂亮的展示箱里放一些钻石进行展示。因为贝蒙希望展示在同一个箱子里的钻石大小尽量相似，所以她决不会把两颗大小相差超过K的钻石一起放进同一个箱子里（如果两颗钻石的大小恰好相差K那它们也能一起放在同一个箱子里展示）。
给出K，请帮助贝蒙求出她能展示在两个箱子里的钻石数量和的最大值。
输入描述 Input Description
输入的第一行包含N和K(0≤K≤10^9)。
接下来的N行每行包含一个整数表示其中一颗钻石的大小。所有的大小都是正数且不超过10^9。
输出描述 Output Description
输出一个正整数，表示贝蒙能展示的钻石数量的最大值。
注意：一个钻石最多只能放入一个展示箱内。
求思路
陈正朔在2021-03-15 12:25:51追加了内容
d
陈正朔在2021-03-15 17:30:09追加了内容
111
0
已采纳
中级启示者
线性DP
核心DP部分
for(int i=1;i<=n;i++){
f1[i]=max(f1[i],f1[i-1]);
}
for(int i=n;i>=1;i--) {
f2[i]=max(f2[i],f2[i+1]);
}
for(int i=1;i<=n;i++){
ans=max(ans,f1[i]+f2[i+1]);
}
0
初级光能
d
