动态规划系列—-最长上升子序列

最长上升子序列

题目描述

这是一个简单的动规板子题。

给出一个由 n(n≤5000) 个不超过 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。

最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。

输入格式

第一行，一个整数n，表示序列长度。

第二行有 n 个整数，表示这个序列。

输出格式

一个整数表示答案。

题目分析1

第一阶段定义dp数组

这里dp数组的定义非常特别，dp[i]表示以a[i]结尾的最长上升子序列的长度。

第二阶段推导状态转移方程。

对于dp[i]而言，如果a[i]>a[j]，说明a[i]可以放在a[j]的右边，那么以以a[i]结尾的最长上升子序列的长度为dp[j]+1。这里的j<i。

第三阶段写代码

（1）初始化。dp[i]至少包含a[i]，所以它一开始的长度为1。

（2）第一层for循环遍历数据规模，这里是遍历给定的序列。

（3）第二层for循环遍历限制，假设第一层遍历到了i，这里是遍历i前面的值。

题目代码1

import java.util.Scanner;
public class Main{
public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	int n = scanner.nextInt();
	int mod = (int) (1e9+7);
	int a[] = new int[n+1];
	int dp1[] = new int[n+1];
	for(int i = 1;i <= n;i++) {
		a[i] = scanner.nextInt();
		dp1[i]=1;
	}
	for(int i = 2;i <= n;i++) {
		for(int j = i-1;j >= 1;j--) {
			if(a[j]<=a[i]) dp1[i] = Math.max(dp1[j]+1, dp1[i]);
		}
	}
	long res = 0;
	for(int i = 2;i <= n;i++) {
		res = Math.max(res, dp1[i]);
	}
	System.out.println(res);
}
}

题目分析2

上一种做法的时间复杂度是，还有另一种做法，类似二分+贪心将时间复杂度控制在。

第一阶段定义dp数组

dp[i]表示长度为i的上升子序列最后一个数的值。

第二阶段推导状态转移方程

如果a[i]>dp[j]，那么说明a[i]可以放在长度为j的序列后面，那么也就是说长度为j+1的上升子序列最后一个数的值是a[i]。否则我用它更新其它dp的值，那么贪心和二分就体现在这里。

我们先来强调几个共识，达成共识之后再去看这道题怎么做。

共识1：长度相同的两个上升序列，最后一个数的值越小它的优势越高。

对于两个长度为3的上升序列，[1,2,3]和[1,2,5]，如果我只能留下一个我要留哪个？对于第二个序列而言，如果我要添加一个数字4，我是添加不进去的，因为5大于4，但是对于第一个序列而言，我就可以添加进去。所以长度相同的两个上升序列，最后一个数的值越小它的优势越高。这是贪心的地方。当a[i]>dp[j]不满足时。说明至少a[i]会遇到一个比自己大的数字，起码已经有了dp[j]就是比a[i]大了嘛（这里暂时不考虑相等的情况）。

共识2：我们定义的dp数组它是递增的。

dp[i]表示长度为i的上升子序列最后一个数的值。那么dp[1]<dp[2]<dp[3]。假设dp[2]>dp[3]，那么长度为2的上升序列最后一个数完全可以加在长度为3的上升序列后面，变成长度为4的上升序列。然后长度为3的上升序列里面第二个数的值可以作为dp[2]，此时dp[2]<dp[3]又满足了。只用文字有点抽象，举个例子。

长度为1的序列为[1]，即dp[1]=1；长度为2的序列为[1,5]，dp[2]=5；长度为3的序列为[1,2,3]，dp[3]=3；

此时dp[2]>dp[3]。但是呢[1,5]里面的5完全可以加在[1,2,3]的后面，此时就有了长度为4的序列[1,2,3,4]，dp[4]=4。那么长度为2的序列应该为[1,2]，[1,5]也是长度为2的序列，但是根据共识1，我们应该选择[1,2]，此时dp[2]=2<dp[3]=3。

共识3：对于一个数a[i]，我想用它来更新dp数组，那么它可以并且只能更新从左向右数第一个比a[i]大的dp值。

更新第一个比a[i]大的dp值，这点是ok的，因为如果a[i]小于dp[j]，又比dp[j]左边的数字大，那么它可以替换掉dp[j]原先的值，让dp[j]记录的数更小，由共识1，也就是让dp[j]更具有优势。

他为什么只能更新第一个比a[i]大的dp值呢？是为了确保更新后的序列依然是上升的。假设dp[j]>a[i]，dp[j+1]>a[i]，dp[j]是第一个大于a[i]的，那么我可以保证j左边的值，都是小于a[i]的。那么我把a[i]插在这个序列里面是没有问题的。但是如果我用a[i]去更新dp[j+1]，j+1左边的数字不小于a[i]，这样a[i]插入这个序列里面会导致序列不是上升的，这是不合题意的更新，不能做。举个例子，

长度为1的序列为[1]，即dp[1]=1；长度为2的序列为[1,3]，dp[2]=3；长度为3的序列为[1,3,5]，dp[3]=5；目前有一个数字2，那么dp[2]>2，dp[3]>2。如果用2更新dp[2]得到的序列是[1,2]，因为2代替了原本的3。如果用2更新dp[3]得到的序列是[1,3,2]，因为2代替了原本的5，但是此时这就不是上升序列了。

如果所有的dp值都比a[i]小，也就是a[i]大于最后一个有效dp，那么其实就是一开始说的“如果a[i]>dp[j]，那么说明a[i]可以放在长度为j的序列后面，那么也就是说长度为j+1的上升子序列最后一个数的值是a[i]。”

现在来谈一下代码吧。

第三阶段写代码

（1）初始化。一开始序列为空，那么dp[0]=0，这种初始化对于java而言一般不用管。

（2）第一层for循环遍历序列

（3）第二层for循环遍历第一个比a[i]大的dp值，那么这里因为dp值是递增的可以用二分去找。

关于dp的初始化大家可能还有一个问题，dp[0]=0没有问题，但是dp[1]=0，dp[2]=0，dp[3]这些也可以吗？如果dp[1]=0，那么a[i]肯定更新dp[1]，这里没有问题。如果dp[1]不等于0且小于a[i]，这时应该是dp[2]=a[i]。这说明我可以在长度为1的序列后面再加一个数字，变成长度为2的序列，此时他最后一个值是a[i]，这里也是符合逻辑的。但凡我遍历到了i，说明i前面的dp值都是小于a[i]的，说明我可以增加序列长度了，此时序列最后一个值是a[i]。

题目代码2

解释一个代码片段，二分的板子就不详细说了，

while(l<r) {
    int mid = (l+r)/2;
    if(dp[mid]<nums) {
        l = mid+1;
    }else {
        r = mid;
    }
}
dp[l] = nums;
if(l == res) {
    res++;
}

这里就是上一部分最后那里解释的地方，在二分的过程中，二分的左右端点分别是1和当前有效序列长度+1，用res记录，+1是因为出现可以增加序列长度时增加序列的长度，所以要给他一个位置。想象一下二分的过程，如果dp值都是小于a[i]的，那么l会不断向右移动，直到l和r相等，此时他们是在当前有效序列长度+1的位置，即l=r=res。退出二分后也就是更新当前有效序列长度+1的位置，说明有效长度增加了，那么res记录的就是当前有效序列长度+1，res应该加一。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int a[] = new int[n+1];
    String strings[] = br.readLine().split(" ");
    for (int i = 0; i < strings.length; i++) {
        a[i+1] = Integer.parseInt(strings[i]);
    }
    System.out.println(LIS(a));
}
private static int LIS(int[] a) {
    int res = 1;
    int n = a.length;
    int[] dp = new int[n];
    for (int i = 1; i < n; i++) {
        int nums = a[i];
        int l = 1;
        int r = res;
        while(l<r) {
            int mid = (l+r)/2;
            if(dp[mid]<nums) {
                l = mid+1;
            }else {
                r = mid;
            }
        }
        dp[l] = nums;
        if(l == res) {
            res++;
        }
    }    
    return res-1;//1 4
}
}