题解 | #Redraiment的走法#
Redraiment的走法
https://www.nowcoder.com/practice/24e6243b9f0446b081b1d6d32f2aa3aa
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 bf = new BufferedReader(new InputStreamReader(System.in)); String str; while((str = bf.readLine()) != null){ int len = Integer.parseInt(str); int[] nums = new int[len]; String[] split = bf.readLine().split(" "); for(int i = 0;i < len;++i){ nums[i] = Integer.parseInt(split[i]); } System.out.println(count(nums)); } } public static int count(int []nums){ int []dp = new int[nums.length+1]; //初始化为1 Arrays.fill(dp,1); int max = 1; for(int i = 1;i < nums.length;++i){ for(int j = 0;j < i;++j){ if(nums[j] < nums[i]){ dp[i] = Math.max(dp[i],dp[j] + 1); } max = Math.max(dp[i],max); } } return max; } }
对count()方法的理解:
定义int []dp;默认每个值都是1,每一个数字自己就是一一步
然后开始循环muns,也就是如图的A[i],从A[1]开始(A[0]前面没有数字,不需要比较),A[1]前面的A[0]:18大于17,所以到A[1]的最大步数还是1,继续循环A[2],和A[0]比较,A[2]大于A[0],所以到A[2]的最大步数就为 dp[0]+1=等于2,是两步,继续比较A[2]大于A[1],所以A[1]到A[2]的最大步数是2步(dp[1]+1),依次往后类推,就能算出来最长步数了