题解 | #Redraiment的走法#

Redraiment的走法

https://www.nowcoder.com/practice/24e6243b9f0446b081b1d6d32f2aa3aa

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int[] arr = new int[a];
        int ii = 0;
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            arr[ii++] = in.nextInt();
        }
        int[] dp = new int[a];  //数组dp[i]表示以第i个元素结尾的最长序列步数,该步数通过动态规划来求解
        dp[0] = 1;
        int dpMax = dp[0];
        for(int i=0; i<a; i++) {
            for(int j=0; j<i; j++) {
                if(arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[j] + 1,dp[i]);
                } else if (dp[i] == 0 && arr[j] >= arr[i]) {  //这里需要初始化为1,看其他答案在循环前就初始化数组为1
                    dp[i] = 1;
                }
            }
            dpMax = Math.max(dpMax, dp[i]);
        }
        System.out.println(dpMax);

    }
}

全部评论

相关推荐

Gaynes:查看图片
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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