蓝桥杯——算法训练——小明爬山

问题描述

你有个同学叫小明，他早听闻祖国河山秀丽，于是有一个爬山的计划，并列了一张所有山的高度表，而又因“人往高处走”的说法，所以他希望爬的每一座山都比前一座要高，并且不能改变山的高度表上的顺序，爬的山数还要最多，请贵系的你帮他解决这个问题。

输入格式

输入第一行为num，代表山的个数
输入第二行有num个整数，代表每座山的高度

输出格式

输出只有一个数，为符合要求的最大爬山数

样例输入

10
1 3 5 7 9 2 4 6 8 10

样例输出

6

解法一、dp

这里dp[i]存储的是到第i个山峰，最长的递增子序列长度

 第一层循环里面嵌套一层for循环，如果height[i]的长度大于height[j]，那么这个子序列就是递增的，此时就要考虑是不是到第i个山峰的时候的最长的递增子序列，即

res = Math.max(res, dp[i])

但是这里时间复杂度达到了O(n²)，导致了只通过了四个测试点 

package com.study.蓝桥杯.算法训练;

import java.util.Scanner;

/**
 * @author sjn
 * @date 2022-2-26
 */

public class ALGO_812小明爬山 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] height = new int[num];

        for (int i = 0; i < num; i++) {
            height[i] = sc.nextInt();
        }

        System.out.println(dp(height));
    }

    public static int dp(int[] height) {
        if (height.length == 0) {
            return 0;
        }

        int[] dp = new int[height.length];
        dp[0] = 1;
        int res = 1;

        for (int i = 1; i < height.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (height[i] > height[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }

解法二、贪心+二分 

 Dynamic programming + Dichotomy可以将时间复杂度降到O(NlogN)

package com.study.蓝桥杯.算法训练;

import java.util.Scanner;

public class ALGO_812小明爬山 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] height = new int[num];

        for (int i = 0; i < num; i++) {
            height[i] = sc.nextInt();
        }

        System.out.println(lengthOfLIS(height));
    }

    //Dynamic programming + Dichotomy.
    public static int lengthOfLIS(int[] height) {
        int[] tails = new int[height.length];
        int res = 0;
        for (int num : height) {
            int i = 0, j = res;
            while (i < j) {
                int m = (i + j) / 2;
                if (tails[m] < num)
                    i = m + 1;
                else
                    j = m;
            }
            tails[i] = num;
            if (res == j)
                res++;
        }

        return res;
    }
}