算法思想之动态规划(六)——最长上升子序列问题

2019-06-03 本文已影响0人复旦猿

前言

今天我们继续讨论经典的动态规划问题之最长上升子序列问题。

最长上升子序列问题

问题描述

给定一个数字序列A，求该序列中最长上升子序列的长度。例如A={1,4,2,5,3}，其最长上升子序列为{1,2,3}，因此最长上升子序列的长度为3。

问题分析

假设序列 $A$ 长度为 $n$ ，构建一个长度为 $n$ 的一维数组 $dp[n]$ ， $dp[i]$ 代表了以 $A[i]$ 结尾的上升子序列的长度。很显然， $dp[i] = 1 + max\{dp[j] | A[j] < A[i] 且 j < i \}$ ，最长上升子序列的长度为 $max\{dp[i] \}$ 。

代码实现

通过问题分析，可以很容易得用代码实现，下面给出算法的java实现。

public class LongestIncreasingSubsequence {

    public int getLIS(int[] A, int n) {
        return core(A, n);
    }

    // 动态规划
    public static int core(int[] A, int n) {
        if (n == 0) {
            return 0;
        }

        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            int max = 0;
            for (int j = 0; j < i; j++) {
                if (A[i] > A[j]) {
                    max = Math.max(max, dp[j]);
                }
            }
            dp[i] = max + 1;
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            if (res < dp[i]) {
                res = dp[i];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        LongestIncreasingSubsequence main = new LongestIncreasingSubsequence();
        int[] A = new int[]{1, 4, 2, 5, 3};
        int n = 5;
        System.out.println(main.getLIS(A, n));
    }
}

经典问题

未来几篇博文，我将继续对经典的动态规划问题进行整理，敬请关注~
由于本人水平有限，文章难免有欠妥之处，欢迎大家多多批评指正！

写在最后

欢迎大家关注我的个人博客复旦猿。