看了大佬的题解:最长递增序列的长度就是第二个问题的答案
参考代码:
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语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:377 |
A+B for Input-Output Practice (III) (C语言代码)浏览:576 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:476 |
C语言程序设计教程(第三版)课后习题6.3 (C++代码)浏览:963 |
三角形 (C语言代码)浏览:914 |
完数 (C语言代码)浏览:693 |
Minesweeper (C语言描述,蓝桥杯)浏览:1127 |
1013题解浏览:561 |
大家好,我是验题君浏览:577 |
矩阵乘方 (C语言代码)浏览:1031 |