参考代码:
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] arr = new int[n + 1]; for(int i = 1; i <= n; i++) arr[i] = scanner.nextInt(); scanner.close(); int[] dp = new int[n + 1]; int[] stack = new int[n + 1]; int indexEnd = 0;//记录答案序列结尾数的下标 int res = 0; for(int i = 1; i <= n; i++) { dp[i] = 1;//arr[i]为一个序列 for(int j = 1; j < i; j++)//以第i个数结尾的最大递增序列长度 { if(arr[j] <= arr[i] && dp[i] < dp[j] + 1)//arr[j] <= arr[i],等于一定不能缺!!! dp[i] = dp[j] + 1; if(dp[i] > res) { res = dp[i]; indexEnd = i; } } } //构造答案序列 int i = indexEnd - 1; int l = res; int index = 0; stack[index++] = indexEnd; while(l > 1) { if(dp[i] == l - 1 && arr[i] <= arr[indexEnd]) { stack[index++] = i; indexEnd = i; l--; } i--; } System.out.println("max=" + res); for(int j = index - 1; j >= 0; j--)//逆序输出 System.out.print(arr[stack[j]] + " "); } }
0.0分
5 人评分
C语言程序设计教程(第三版)课后习题9.1 (C++代码)浏览:562 |
点我有惊喜!你懂得!浏览:4107 |
C语言训练-求素数问题 (C语言代码)浏览:956 |
C语言训练-角谷猜想 (C语言代码)浏览:1705 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:609 |
数组输出 (C语言代码)--此题的题目描述有问题浏览:1816 |
WU-拆分位数 (C++代码)浏览:779 |
C语言程序设计教程(第三版)课后习题6.5 (C++代码)浏览:449 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:551 |
C语言程序设计教程(第三版)课后习题12.1 (C语言代码)浏览:645 |