前言:平时我们做的题目都是用动态规划做的,但是有没有能够优化一下呢?
有一个结论,长度为 i 的一个序列,最后一个元素一定是构成长度为 i 的序列中最小的
我们可以用二分来优化
题目地址
#include<bits/stdc++.h>
using namespace std;#define int long long
const int N = (int)5e5+10;
int a[N];
int le[N],rig[N];
int n;// 考虑用
signed main(){cin >> n;for(int i=1;i<=n;i++){cin >> a[i];}vector<int> re;le[1] = 1;re.push_back(a[1]);for(int i=2;i<=n;i++){int u = a[i];if(u>=re[re.size()-1]){re.push_back(u);le[i] = re.size();}else{int pos = upper_bound(re.begin(),re.end(),u) - re.begin();re[pos] = u;le[i] = pos + 1; }}re.clear();le[1] = 1;re.push_back(a[n]);for(int i=n-1;i;i--){int u = a[i];if(u>re[re.size()-1]){re.push_back(u);rig[i] = re.size();}else{int pos = upper_bound(re.begin(),re.end(),u) - re.begin();re[pos] = u;rig[i] = pos+1;}}int ans = 0;for(int i=1;i<=n;i++){ans = max(le[i]+rig[i]-1,ans);}cout << ans;system("pause");return 0;
}