题目主要信息

1、多组数据，每组有两行数据，第一行为输入数组的个数，第二行输入数组内容

2、找到可以走的步数最多的步数

方法一：暴力用动态规划

具体做法

看到题目我们可以将其理解为求解最长递增子序列的问题，显然就是dp的问题，dp[i]表示到元素i结尾时，最长的子序列的长度。

如下例子[2 5 1 5 4 5]

Java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    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;
    }
    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));
        }
    }
}

复杂度分析

• 时间复杂度：$O(n^2)O(n^2)$，两层for循环遍历
• 空间复杂度：$O(n)O(n)$，数组dp的大小。

方法二：基于二分的动态规划

具体做法

这个思路也是之前做最长递增子序列问题学到的，可以使用一个二分查找进行优化动态规划，这样的话时间复杂度就会降低很多。

需要两个辅助数组dp与end，dp存储每个元素的最大子序列个数，end存列表的最大子序列(下标从1开始)

dp存储每个元素往前的最长子数列大小 $dp[i]=max(dp[i],dp[j]+1)dp[i]\; =\; max(dp[i],\; dp[j]+1)$ $jj$ 为$0-i-10-i-1$中比$arr[i]arr[i]$小的子数列数据 为了避免重复比较,用end数组存储最长上升子序列， 当$arr[i]>end[len]arr[i]\; >\; end[len]$ 时 $arr[i]arr[i]$添加到 $endend$后面 否则 从$end0->lenend\; 0->len$范围内查找到第一个比 $arr[i]arr[i]$大的元素 进行替换， 此处采用二分法查找。

Java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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(LIS(nums));
        }
    }
       public static int LIS (int[] arr) {
        int n = arr.length;
        // 列表的最大子序列 下标从1开始
        int[] end = new int[n+1];
        // 存储每个元素的最大子序列个数
        int[] dp = new int[n];
        int len = 1;
        //子序列的第一个元素默认为数组第一个元素
        end[1] = arr[0];
        //第一个元素的最大子序列个数肯定是1
        dp[0] =1;
        for(int i =1; i< n; i++){
            if(end[len] < arr[i]){
                //当arr[i] > end[len] 时 arr[i]添加到 end后面
                end[++len] = arr[i];
                dp[i] = len;
            }else{
                // 当前元素小于end中的最后一个元素 利用二分法寻找第一个大于arr[i]的元素
                // end[l] 替换为当前元素 dp[]
                int l = 0;
                int r = len;
                while(l <= r){
                    int mid = (l+r)>>1;
                    if(end[mid] >= arr[i]) {
                        r = mid - 1;
                    }else l = mid +1;
                }
                end[l] = arr[i];
                dp[i] = l;
            }
        }
        int[]  res = new int[len];
        for(int i = n-1; i>=0; i--){
            if(dp[i] == len){
                res[--len] = arr[i];
            }
        }
        return res.length;
    }

}

复杂度分析

• 时间复杂度：$O(nlo{g}_2(n))O(nlog\_2(n))$，遍历一次，在使用二分查找为$O(lo{g}_2(n))O(log\_2(n))$
• 空间复杂度：$O(n)O(n)$，借助了辅助空间dp与end