VOLIS - Dãy con không giảm dài nhất
Tác giả: flashmt
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#define oo 2000000001
using namespace std;
int main()
{
int n,d,a[1010],last[1010];
cin >> n >> d;
for (int i=0;i<=1000;i++) last[i]=(i?oo:-oo);
for (int i=1;i<=n;i++)
{
cin >> a[i];
for (int j=i;j;j--)
if (a[i]-d>last[j-1]) last[j]=min(last[j],a[i]-d);
else
if (a[i]+d>=last[j-1]) last[j]=min(last[j],last[j-1]);
}
for (int ans=n;ans;ans--)
if (last[ans]!=oo)
{
cout << ans << endl;
return 0;
}
}