8.15 著名问题---最长递增子序列的长度 以及 小结

解法一：暴力法

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;public class Main {/* * 思路：暴力法 * 依次将数组中的元素作为开头，寻找第一个比其大的元素i1，再从i1开始向后查找第一个比其大的...，直到查完所有元素输入数据：4 2 3 1 5* */ public static void main(String[] args) {//（1）输入相关数据Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] a = new int[n];for(int i=0;i<n;i++) {a[i]=sc.nextInt();}int ans = f(a);System.out.println(ans);}private static int f(int[] a) {int max=0;for(int i=0;i<a.length;i++) {int p=i;int cnt=1;for(int j=i+1;j<a.length;j++) {if(a[j]>a[p]) {cnt++;p=j;}}//forif(cnt>max) {max=cnt;}}return max;}}

解法二：dp动态规划

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;public class Main {/* * 思路：动态规划输入数据：4 2 3 1 5* */ static int[] dp;//dp[i]：存放以i个元素结尾的序列中，最长的递增子序列（下标从0开始）public static void main(String[] args) {//（1）输入相关数据Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] a = new int[n];for(int i=0;i<n;i++) {a[i]=sc.nextInt();}//（2）获取dp表dp = new int[n];dp[0]=1;for(int i=1;i<n;i++) {//以第i个元素作为结尾int max=1;//初始最长递增子序列长度为1（ai本身）for(int j=i-1;j>=0;j--) {//ai前的元素aj依次与ai进行比较if(a[j]<a[i]) {//该元素比ai小max = Math.max(max, dp[j]+1);}}//fordp[i]=max;}System.out.println(dp[n-1]);}}

小结：