最长不下降子序列—递归输出最长链

xiaoxiao2021-02-28  5

#include<bits/stdc++.h> using namespace std; int n,f[107][4],maxx,maxl; int dg(int n) { if(f[n][3]==0) cout<<f[n][1]<<" "; else { dg(f[n][3]); cout<<f[n][1]<<" "; } } int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>f[i][1]; f[i][2]=1; f[i][3]=0; } for(int i=2;i<=n;i++) for(int j=1;j<=i;j++) { if(f[i][1]>f[j][1] && (f[j][2]+1>f[i][2])) { f[i][2]=f[j][2]+1; f[i][3]=j; if(f[i][2]>maxx) { maxx=f[i][2]; maxl=i; } } } cout<<"max="<<maxx<<endl; dg(maxl); }
转载请注明原文地址: https://www.6miu.com/read-200360.html

最新回复(0)