题解 | #Redraiment的走法#
Redraiment的走法
https://www.nowcoder.com/practice/24e6243b9f0446b081b1d6d32f2aa3aa
import java.util.Scanner; import java.util.List; import java.util.ArrayList; import java.util.Map; import java.util.HashMap; public class Main { static int[] arr; // 存输入信息 static int length = 0; // 最大步数 static int num; static Map<Integer, Integer> map = new HashMap<>(); // 字典,key:位置 value:该位置处,后续最大步数 public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextInt()) { // 注意 while 处理多个 case num = in.nextInt(); arr = new int[num]; for (int i = 0; i < num; i++) { arr[i] = in.nextInt(); } map.put(num - 1, 1); for (int j = num - 1; j >= 0; j--) { dfs(j); } System.out.println(length); } } // index:当前求解位置 static void dfs(int index) { int max = 1; for (int i = index + 1; i < num; i++) { if (arr[index] < arr[i]) { int step = map.get(i) + 1; if (step > max) { max = step; } } } map.put(index, max); if (max > length) { length = max; } } }