题目描述:
设计一个O(N^2)算法,找出n个数据组成的序列的最长单调递增子序列。
输入示例:
8
1 2 3 -9 3 9 0 11
输出示例:
5
1 2 3 9 11
设计思路:
有一个数组 a[n],用 dp[i] 表示以 a[i] 结尾的最长单调子序列的长度,可以知道初始化值为1,如果存在比 a[i] 小的数 a[j] 满足a[j] < a[i] 且 j<i 且 dp[j] + 1 > dp[i],则产生新的最长子序列,可以得到递推公式:dp[i] = max (1, dp[j] + 1),需要从1到 i - 1枚举 j 的值求最大值。时间复杂度:O(N^2)
Java代码:
import java.util.Scanner;/*** 动态规划,求最长单调递增子序列*/public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n;n = scanner.nextInt();//存放最长子序列的长度int[] dp = new int[n];int[] a = new int[n];int maxLength = -1; //最长长度int maxIndex = -1; //递增最长子序列的最后一值的下标int[] preIndex = new int[n]; //每一个dp[i]的前一个值的下标for(int i = 0; i < n; i++) {a[i] = scanner.nextInt();//初始值为1,即只有一个值时的长度dp[i] = 1;preIndex[i] = -1;}for(int i = 0; i < n; i++) {for(int j = 0; j < i; j++) {if(a[j] < a[i] && (dp[j] + 1) > dp[i]) {dp[i] = dp[j] + 1;preIndex[i] = j;}}if(dp[i] > maxLength) {maxLength = dp[i];maxIndex = i;}}System.out.println(maxLength);int[] res = new int[maxLength];for(int i = maxIndex, j = 0; i != -1; j++) {res[j] = a[i];i = preIndex[i];}for(int i = res.length - 1; i >= 0; i--) {System.out.print(res[i] + " ");}}}