LIS 优化思路
显然最长上升子序列问题朴素解法是O(n^2),在此题是会TLE :
// 定义 f[i] 表示以 前i个元素构成的子序列中以a[i]结尾的最长上升子序列长度
for(int i = 1 ; i <= n ; i++)
for(int j = 0 ; j < i ; j++)
if ( a[j] < a[i] )
f[i] = max(f[i] , f[j] + 1 ) ;
优化可以从第二层循环进行
可以通过线段树等方式维护区间[1 , a[i] - 1] f数组的最大值
这样整体时间复杂度O(NlogN)
近期例题:
Atcoder ABC339E 更改为维护区间 [a[i] - dist , a[i] + dist] 内 f 数组的最大值即可 : )
#include <bits/stdc++.h>
#define ls ( x << 1 )
#define rs ( x << 1 | 1 )
using namespace std;
const int N = 2e5 + 10 ;
int f[N << 2] , n , a[N] , bin[N] ;
void update(int x) {
f[x] = max(f[ls] , f[rs]) ;
}
void change(int pos,int v,int l,int r,int x) {
if ( l == r ) {
f[x] = v ;
return ;
}
int mid = ( l + r ) >> 1 ;
if ( pos <= mid ) change(pos , v , l , mid , ls) ;
else change(pos , v , mid + 1 , r , rs) ;
update(x) ;
}
int query(int A,int B,int l,int r,int x) {
if ( A > B ) return 0 ;
if ( l > r ) return -1 ;
if (A <= l && r <= B) return f[x] ;
int mid = ( l + r ) >> 1 , ret = 0 ;
if ( A <= mid ) ret = max(ret , query(A,B,l,mid,ls)) ;
if ( mid < B ) ret = max(ret , query(A,B,mid+1,r,rs)) ;
return ret ;
}
int main()
{
cin.tie(nullptr)->ios::sync_with_stdio(false);
cin >> n ;
for(int i = 1 ; i <= n ; i++) {
cin >> a[i] ;
bin[i] = a[i] ;
}
sort(bin + 1 , bin + n + 1) ;
int m = unique(bin + 1 , bin + n + 1) - bin - 1 ;
for(int i = 1 ; i <= n ; i++) {
int x = lower_bound(bin + 1 , bin + m + 1 , a[i]) - bin ;
change(x , query(1 , x - 1 , 1 , m , 1) + 1 , 1 , m , 1) ;
}
cout << query(1 , m , 1 , m , 1) << '\n' ;
return 0 ;
}