题解 | #最长上升子序列(一)#

最长上升子序列(一)

https://www.nowcoder.com/practice/5f65ccbb025240bd8458eb6479c2612e

总结:
计算i处的最长升序子序列len[i],等于i之前所有的子序列(末尾元素大于arr[i])中最大子序列+1
根据上述状态转换使用动态规划解决该问题。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        int[] len = new int[n];//最长上升序列长度
        Arrays.fill(len,1);
        int max = 0;
        for(int i=1;i<n;i++){
            max = 0;
            for(int j=0;j<i;j++){
                if(arr[i]>arr[j]){
                    max = Math.max(max,len[j]);
                }
            }
            len[i] = max+1;
        }
        int res = 0;
        for(int i=0;i<n;i++)
            res = Math.max(res,len[i]);
        System.out.println(res);
    }
}
全部评论

相关推荐

07-07 12:47
门头沟学院 Java
码农索隆:竟然还真有卡体检报告的
点赞 评论 收藏
分享
07-11 22:27
中南大学 Java
程序员牛肉:学历的话没问题。但是没问题的也就只有学历了。 其实你的整体架构是正确的,博客接着干。但是项目有点过于简单了。从后端的角度上讲,你这也就是刚入门的水平,所以肯定约面试够呛。 如果你要应聘后端岗位,那你第一个项目竟然是仿写操作系统。这个你要面试官咋问你。你一定要记住一点,你简历上写的所有的东西,都是为了证明你有能力胜任当前的岗位,而不是为了证明你自己会什么。 如果你只是浅浅的做几个项目,描述也都是烂大街。技术点也都是各种混水类的配置类需求,那你就不要幻想自己能走多远。一定要保持思考,保持学习。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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