题解 | #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),依次往后类推,就能算出来最长步数了

全部评论

相关推荐

找个工作&nbsp;学历是要卡的&nbsp;要求是高的&nbsp;技能不足是真的&nbsp;实习经验是0的&nbsp;简历无处可写是事实的&nbsp;钱不好赚是真的&nbsp;想躺平又不敢躺&nbsp;也不甘心躺&nbsp;怕自己的灵感和才华被掩埋甚至从未被自己发现&nbsp;又质疑自己是否真正有才华
码农索隆:你现在啊,你心里都明白咋回事,但是你没办法改变现状,一想到未来,你又没有信心狠下心来在当下努力。 得走出这种状态,不能一直困在那里面,哪不行就去提升哪,你一动不动那指定改变不了未来,动起来,积少成多才能越来越好
点赞 评论 收藏
分享
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务