DP or 贪心 + 二分答案：最长上升子序列Ⅰ

文章目录

DP or 贪心 + 二分答案：最长上升子序列Ⅰ

问题

思路

DP（ O(n ^ 2）)

一个数若能加入在其之前的某个上升子序列，则该数一定大于位于其之前的某上升子序列的最后一个元素（最大的元素）。我们用DP[i]表示以第i个数结尾的最长上升子序列的长度。那么DP[i]是如何经状态转移得到的呢？设数组为a[]，对于第i个数a[i]，它有可能加入在其之前以任意某个数a[j]结尾的上升子序列，也就是说DP[i]可能由DP[j]转移得到，这里需满足j < i,a[i] > a[j]。那么状态转移方程为：

即状态转移时，我们需往前面遍历，找到一个a[i]>a[j]，且DP[j]最大的，将其继承过来，也就是将a[i]加入其代表的上升子序列

代码

import java.util.*;

public class Main {
    static int[] array = new int[1005];
    static int[] dp = new int[1005];
    public static void main(String[] args) {
        int n, ans, i, j;
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            n = scanner.nextInt();
            for (i = 1;i <= n;i++) {
                array[i] = scanner.nextInt();
            }
            Arrays.fill(dp, 0);
            ans = 0;
            for (i = 1;i <= n;i++) {
                for (j = 0;j < i;j++) {
                    if (array[i] > array[j]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
                ans = Math.max(ans, dp[i]);
            }
            System.out.println(ans);
        }
    }
}

贪心 + 二分答案(最优解，O(nlogn))

考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

基于上面的贪心思路，我们维护一个数组 d[i] ，表示长度为 i 的最长上升子序列的末尾元素的最小值，用 len 记录目前最长上升子序列的长度，起始时 len 为 1，d[1] = nums[0]。

贪心思想，对于每个数x，要把它放到小于当前x的最大的d[len]后，之后更新长度len

设当前已求出的最长上升子序列的长度为 len（初始时为 1），从前往后遍历数组 nums，在遍历到 nums[i] 时：

在 d 数组中二分查找，找到第一个比 nums[i] 小的数 d[k] ，并更新 d[k + 1] = nums[i]，再更新长度len。

d[i]数组是单调的，因此可以用二分查找（证明可以用反证法）

代码

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            int[] array = new int[n];
            int i, len = 0;
            for (i = 0; i < n; i++) {
                array[i] = scanner.nextInt();
            }
            int[] d = new int[n + 1];
            for (i = 0; i < n; i++) {
                int l = 0;
                int r = len;
                while (l < r) {
                    int mid = (l + r + 1) / 2;
                    if (d[mid] < array[i]) {
                        l = mid;
                    } else {
                        r = mid - 1;
                    }
                }
                d[l + 1] = array[i];
                len = Math.max(len, l + 1);
            }
            System.out.println(len);
        }
    }


}