1. 题目描述

图片来源：

 

2. 代码

方法1（动态规划）81%超时　　

import java.util.Scanner;

public class Main{     private static int N;//序列长度    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        N = sc.nextInt();        int [] val = new int[N];//正整数        for (int i = 0; i < N; i++) {            val[i] =  sc.nextInt();        }       int max = 0;       int [] dp = new int[N];       for (int i = 0; i < N; i++) {           for (int j = 0; j < i; j++) {             if(val[j]

方法二，AC 100　

import java.util.Scanner;

public class Main {    private static int N;//序列长度    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        N = sc.nextInt();        int [] val = new int[N];//正整数        for (int i = 0; i < N; i++) {            val[i] =  sc.nextInt();        }        int max = 0;        int [] dp = new int[N];        for(int num: val){           //二分找位置           int j = Arrays.binarySearch(dp, 0,max,num);           //找不到新增           j = j<0? -(j+1) : j;           dp[j] = num;           max = j== max?(++max):max;        }        System.out.println(max);    }   }

方法三，自己写二分查找

import java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int n = scanner.nextInt();        int[] number = new int[n];        for (int i = 0; i < n; i++) {            number[i] = scanner.nextInt();        }        System.out.println(lengthOfLIS(number));    }    public static int lengthOfLIS(int[] nums) {        int[] top = new int[nums.length];        int piles = 0;        for (int i = 0; i < nums.length; i++) {            int poker = nums[i];             /***** 搜索左侧边界的二分查找 *****/            int left = 0, right = piles;            while (left < right) {                int mid = (left + right) / 2;                if (top[mid] > poker) {                    right = mid;                } else if (top[mid] < poker) {                    left = mid + 1;                } else {                    right = mid;                }            }            if (left == piles) piles++;            top[left] = poker;        }        return piles;    }}

方法四

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;public class Main{    public static void main(String[] args) throws IOException {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        int n = Integer.valueOf(br.readLine().trim());        long[] nums = new long[n];        long[] dp = new long[n];        for(int i = 1; i <= n; i++) {            long temp = Long.valueOf(br.readLine().trim());            nums[i] = temp;        }             for(int i = 0; i < n; i++) {            long max = 1;            for(int j = 0; j < i; j++) {                max = Math.max(max, dp[j]+1);            }            dp[i] = max;        }        System.out.println(Arrays.stream(dp).max().orElse(0));    }}

 

 

网址：