权值线段树+离散化+动态规划，时间复杂度O(nlogn)

解题思路:权值线段树+离散化+动态规划

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

#define maxn 100010

#define maxk 100010

int n,k,a[maxn],b[maxn],ans;

int dp1[maxn],dp2[maxn];//dp1[i]表示从前往后以a[i]结尾的最长不下降子序列的长度

//dp2[i]表示从后往前以a[i]结尾的最长不上升子序列的长度

int tree[maxn<<2];

void build(int o,int l,int r){

    tree[o]=0;

    if(l==r)return;

    int mid=(l+r)>>1;

    build(o<<1,l,mid);

    build(o<<1|1,mid+1,r);

}

void update(int o,int l,int r,int x,int val){//将tree[x]更新为val,并随着更新树

    if(l==r){

        tree[o]=max(tree[o],val);

    }

    else{

        int mid=(l+r)>>1;

        if(x<=mid)update(o<<1,l,mid,x,val);

        else update(o<<1|1,mid+1,r,x,val);

        tree[o]=max(tree[o<<1],tree[o<<1|1]);

    }

}

int query(int o,int l,int r,int L,int R){//返回[L,R]的最大的tree[o]

    if(L<=l&&r<=R)return tree[o];

    //if(l>R||r<L)return 0;//这种情形不可能成立

    int mid=(l+r)>>1,ret=0;

    if(mid>=L)ret=query(o<<1,l,mid,L,R);

    if(mid+1<=R)ret=max(ret,query(o<<1|1,mid+1,r,L,R));

    return ret;

}

int main(){

    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++)scanf("%d",&a[i]);

    if(k+1>=n){

        printf("%d",n);

        system("pause");

        return 0;

    }

    for(int i=1;i<=n;i++)b[i]=a[i];

    sort(b+1,b+1+n);

    int tot=unique(b+1,b+1+n)-(b+1);

    for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+tot,a[i])-b;

    build(1,1,tot);

    for(int i=1;i<=n;i++){

        dp1[i]=query(1,1,tot,1,a[i])+1;

        update(1,1,tot,a[i],dp1[i]);

    }

    build(1,1,tot);

    for(int i=n;i>k;i--){

        ans=max(ans,dp1[i-k]+k+query(1,1,tot,a[i-k],tot));

        dp2[i]=query(1,1,tot,a[i],tot)+1;

        update(1,1,tot,a[i],dp2[i]);

    }//最终答案的形式一定是1.  dp1[x]+k+第x+k+1到第n个元素的满足a[y]>=a[x]最大的dp2[y]

    //可以用反证来证明，假如不是，那么ans=dp1[x]+k+第x+k+?到第n个元素的满足a[y]>=a[x]最大的dp2[y],?>1

    //那么由于所有的1.的最大值显然>=ans,所以ans只能是所有的1.的最大值，所以ans是1.的形式

    printf("%d",ans);

    system("pause");

    return 0;

}