看了大佬的题解:最长递增序列的长度就是第二个问题的答案
参考代码:
import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); ArrayList<Integer> arr = new ArrayList<>(); while(scanner.hasNextInt()) arr.add(scanner.nextInt()); scanner.close(); System.out.println(lengthOfLDS(arr)); System.out.println(lengthOfLIS(arr)); } static int lengthOfLDS(ArrayList<Integer> arr)//最长递减序列的长度 { int n = arr.size(); int[] dp = new int[n]; int maxLen = 1; for(int i = 0; i < n; i++) { dp[i] = 1; for(int j = 0; j < i; j++) if(arr.get(i) <= arr.get(j))//由题可知,可以相等 dp[i] = Math.max(dp[i], dp[j] + 1); maxLen = Math.max(maxLen, dp[i]); } return maxLen; } static int lengthOfLIS(ArrayList<Integer> arr)//最长递减序列的长度 { int n = arr.size(); int[] dp = new int[n]; int maxLen = 1; for(int i = 0; i < n; i++) { dp[i] = 1; for(int j = 0; j < i; j++) if(arr.get(i) > arr.get(j)) dp[i] = Math.max(dp[i], dp[j] + 1); maxLen = Math.max(maxLen, dp[i]); } return maxLen; } }
0.0分
5 人评分
最小公倍数 (C语言代码)浏览:863 |
成绩转换 (C语言代码)浏览:1005 |
C语言程序设计教程(第三版)课后习题6.8 (C语言代码)浏览:763 |
C语言训练-求函数值 (C语言代码)浏览:573 |
【计算球体积】 (C语言代码)浏览:1101 |
C语言程序设计教程(第三版)课后习题9.3 (C语言代码)浏览:2092 |
Cylinder (C语言描述,蓝桥杯)浏览:1247 |
sizeof的大作用 (C语言代码)浏览:1449 |
DNA (C语言代码)浏览:391 |
C语言程序设计教程(第三版)课后习题9.3 (C语言代码)浏览:594 |