import java.util.Scanner; public class TestLIS{ private int n; private int array[]; private int lis[]; public TestLIS(int n,int[] array){ this.n=n; this.array=array; lis=new int[n]; } public static void main(String[] args) { Scanner in=new Scanner(System.in); int n=in.nextInt(); int[] array=new int[n]; for(int i=0;i<n;i++){ array[i]=in.nextInt(); } TestLIS tl=new TestLIS(n,array); int maxl=tl.lis(); System.out.println("最长单调递增子序列长度:"+maxl); System.out.println(); System.out.println("最长单调递增子序列构成"); int k=tl.max(); tl.print(k); System.out.println(); } //求数组最长递增子序列 public int lis() { for(int i =0;i< n;i++) { lis[i]=1; for(int j=0;j< i;j++) { if(array[j]< array[i]&&(lis[j]+1>lis[i])) lis[i]=lis[j]+1; } } int max=0; for(int k=0;k< lis.length;k++) { if(lis[k]>max) max=lis[k]; } return max; } //求数组中最大值下标 private int max() { int max = lis[0]; int k = 0; for (int i = 0; i < lis.length; i++) { if (max < lis[i]) { max = lis[i]; k = i; } } return k; } //输出 public void print(int k) { for (int i = k - 1; i >= 0; i--) { if (lis[k] == lis[i] + 1 && array[i] <= array[k]) { print(i); break; } } System.out.print(array[k] + " "); } }
0票
开心
0票
板砖
0票
感动
0票
有用
0票
疑问
0票
难过
0票
无聊
0票
震惊
顶
踩