贝壳：月光宝盒的密码（二分查找,暴力破解,动态规划）

1. 题目描述

图片来源：https://www.nowcoder.com/discuss/220718?type=0&order=0&pos=5&page=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]

dp[i] = Math.max(dp[i],dp[j]+1);

max = Math.max(max, dp[i]);

}

}

}

System.out.print(max+1);

}

}

方法二，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));

}

}

网址：

https://www.nowcoder.com/discuss/220718?type=0&order=0&pos=5&page=1

https://www.nowcoder.com/discuss/220715?type=0&order=0&pos=2&page=1