LIS:由贪心的思想，用dp[len]保存长度为len的子序列中结尾最小的那个值。比如第i个位置的数为x,它与那些1~i-1中的结尾小于x的子序列构成新的子序列。遍历dp，找到第一个大于x的位置pos(知$x>dp[pos-1],x<dp[pos]$)，更新其值为x，即对应长度的子序列结尾值被更新(变得更小)。
LIS的各种变体对应解决策略 $O(n^2)$：

• 最长上升子序列 lower_bound()
• 最长不上升子序列 dp数据乘以-1，upper_bound()
• 最长下降子序列 dp数据乘以-1，lower_bound()
• 最长不下降子序列 upper_bound()

STL二分搜索:
头文件 #include< algorithm>
upper_bound(first,last,val)：返回从first到last的左闭右开区间中第一个大于 val的位置。
lower_bound(first,last,val)：返回从first到last的左闭右开区间中第一个大于等于 val的位置。

方法1

$r[1]\sim r[i]$复杂度为$O(n^2)$,$r[i]\sim r[n]$复杂度为$O(nlogn)$

#include<iostream>
#include<stdio.h> 
#include<string.h>
#include<algorithm>
using namespace std;
int dp[1010];
int r[1010];
int main(){//freopen("in.txt","r",stdin);int n;cin>>n;int index = 0;for(int i = 1;i<=n;i++){cin>>r[i];}int M = 0;int ans = 0;for (int i = 1;i<=n;i++){ans = 0;memset(dp,0,sizeof(dp)); for(int p =1;p<=i;p++){ // 计算从 r[1]~ r[i] 的最长不上升子序列 dp[p] = 1;//  单个节点也可视为长为1的序列，初始化为1  for(int q = 1;q<p;q++){if(r[p]<=r[q]){dp[p] = max(dp[p],dp[q]+1);}}ans = max(ans,dp[p]);}//cout<<i<<'\n';//cout<<ans<<'\n';int len = 1; // LIS 最大值 dp[i+len] =r[i];for(int p = i+1;p<=n;p++){ //计算 从 r[i]~ r[n]的最长不下降子序列 if(r[p]>=dp[i+len]){dp[++len+i] = r[p];}else{int pos = upper_bound(dp+i+1,dp+i+len+1,r[p])-dp;dp[pos] = r[p];}}//cout<<len<<"\n\n";if(len+ans-1>=M){M =len+ans-1;}}cout<<n-M<<"\n";return 0;
}

方法2

总体复杂度为$O(nlogn)$

#include<iostream>
#include<stdio.h> 
#include<string.h>
#include<algorithm>
using namespace std;
int dp[1010];
int r[1010];
int main(){//freopen("in.txt","r",stdin);int n;cin>>n;int index = 0;for(int i = 1;i<=n;i++){cin>>r[i];}int M = 0;int ans = 0;for (int i = 1;i<=n;i++){memset(dp,0,sizeof(dp));ans = 0;int len =1;dp[len] = -r[1]; for(int p =2;p<=i;p++){ // 计算从 r[1]~ r[i] 的最长不上升子序列 if(r[p]<=-dp[len]){dp[++len] = -r[p];}else{int pos = upper_bound(dp+1,dp+len+1,-r[p])-dp;dp[pos] = -r[p];}}ans = len;len = 1; // LIS 最大值 dp[i+len] =r[i];for(int p = i+1;p<=n;p++){ //计算 从 r[i]~ r[n]的最长不下降子序列 if(r[p]>=dp[i+len]){dp[++len+i] = r[p];}else{int pos = upper_bound(dp+i+1,dp+i+len+1,r[p])-dp;dp[pos] = r[p];}}//cout<<len<<"\n\n";if(len+ans-1>=M){M =len+ans-1;}}cout<<n-M<<"\n";return 0;
}

方法3

总体复杂度为$O(n^2)$

#include<iostream>
#include<stdio.h> 
#include<string.h>
#include<algorithm>
using namespace std;
int dp[1010];
int r[1010];
int main(){freopen("in.txt","r",stdin);int n;cin>>n;int index = 0;for(int i = 1;i<=n;i++){cin>>r[i];}int M = 0;int ans = 0;for (int i = 1;i<=n;i++){ans = 0;memset(dp,0,sizeof(dp)); for(int p =1;p<=i;p++){dp[p] = 1;//  单个节点也可视为长为1的序列，初始化为1  for(int q = 1;q<p;q++){if(r[p]<=r[q]){dp[p] = max(dp[p],dp[q]+1);}}ans = max(ans,dp[p]);}int len = 0;for(int p = i;p<=n;p++){dp[p] =1;for(int q =i;q<p;q++){if(r[p]>=r[q]){dp[p] = max(dp[p],dp[q]+1);}}len = max(len,dp[p]);}if(len+ans-1>=M){M =len+ans-1;}}cout<<n-M<<"\n";return 0;
}

方法4

官方推荐做法，总体复杂度为$O(n^2)$,
引用出处

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[1010];
int dp2[1010];
int dp1[1010];
int n;
int main()
{   cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}memset(dp1,0,sizeof(dp1));for(int i=1;i<=n;i++){dp1[i]=1;for(int j=1;j<i;j++){if(a[j]>=a[i])dp1[i]=max(dp1[i],dp1[j]+1);}}memset(dp2,0,sizeof(dp2));for(int i=n;i>=1;i--){dp2[i]=1;for(int j=n;j>i;j--){if(a[j]>=a[i])dp2[i]=max(dp2[i],dp2[j]+1);}}int ans[1010];for(int i=1;i<=n;i++){ans[i]=n-(dp1[i]+dp2[i]-1);}int minn=0x3f3f3f3f;for(int i=1;i<=n;i++){if(minn>ans[i])minn=ans[i];}cout<<minn;return 0;
}