力扣之最长上升子序列 2022-02-28~03-06

JavaScript017

力扣之最长上升子序列 2022-02-28~03-06,第1张

注意dp的定义以及为什么要排序

定义 为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度， 注意必须被选取。

同上，先按照第一维进行排序，然后在第二维寻找LIS

排序的意义 ：通过对第一维进行排序，在动态规划求 的过程中，使得所有可能满足的前面的嵌套都已经求完， 不存在后面的信封能放在前面的任何一个信封里面 ，例如 [[5,4],[6,4],[6,7],[2,3]] ，最后一个信封能放在前面的信封里

和上面一模一样，复杂度也是

排序也 只用排第一维 ，因为 排序的意义在于遍历后面的箱子时确保前面的结果不会再改变了

经典的LIS问题.

但从算法实现角度来看是不难的,可以有较简单的DP,O(n^2)

但数据量一大,TLE是必然的.

辅之以二分,可以优化至O(nlogn)

当然从你题目上可以看出,简单形式的也是可以胜任的.

下面这个是O(nlogn)

不懂可以再问,不过实践上你可以向任何一个ACMer或中学生OI选手请教.

#include<iostream>

using namespace std

#define _cp(a,b) ((a)<(b))

int ans[501],a[501]

int subseq(int n,int* a,int* ans){

int b[501],p[501],i,l,r,m,ret=0

for (i=0i<np[b[l]=i++]=b[l-1],ret+=(l>ret))

for (m=((l=1)+(r=ret))>>1l<=rm=(l+r)>>1)

if (_cp(a[b[m]],a[i]))

l=m+1

else

r=m-1

for (m=b[i=ret]ians[--i]=a[m],m=p[m])

return ret

}

int main(){

int n,Tcin>>T

while(T--&&cin>>n){

for (int i=0i<n&&cin>>a[i]++i)

int mlen=subseq(n,a,ans)

cout<<mlen<<endl

for (int i=0i<mlen++i)

if(i!=mlen-1)

cout<<ans[i]<<' '

else

cout<<ans[i]<<endl

cout<<endl}

}