最长不下降子序列详解

一、什么是最长不下降子序列

最长不下降子序列（Longest Increasing Subsequence，简称LIS）是指在一个序列中，找出一个最长的子序列满足单调递增。其中的单调递增是指数列中后一个数大于前一个数的情况。比如序列[3,1,4,1,5,9,2,6,5,3,5,8,9,7]的最长不下降子序列是[1,2,3,5,8,9]。

二、最长不下降子序列的求解方法

我们介绍两种方法：动态规划和二分查找法。

1. 动态规划法

动态规划的实现是通过维护一个计数数组dp，用来记录以每个元素为结尾的子序列中最长的LIS长度。我们先初始化dp数组为1，因为每个单独的元素的LIS都是1。

int lengthOfLIS_dp(int* nums, int numsSize) {
    if(numsSize <= 1) return numsSize;

    int dp[numsSize];
    for(int i=0; i<numsSize; i++) dp[i] = 1;

    int maxLen = 1;
    for(int i=1; i<numsSize; i++) {
        for(int j=0; j<i; j++) {
            if(nums[j] maxLen) ? dp[i] : maxLen;
    }

    return maxLen;
}

该算法的时间复杂度是O(n^2)，空间复杂度是O(n)。

2. 二分查找法

该方法需要维护一个数组tails，其中tails[i]保存长度为i+1的LIS的最小末尾元素。由于tails长度是不断增加的，因此我们需要一个变量size来维护tails的当前有效长度。

每次遍历数组nums，对于每个元素num，我们在tails中寻找第一个大于等于num的位置index，将tails[index]更新为num，如果index等于size，则表明新增了一条长度为size+1的LIS，需要将size加1。

int lengthOfLIS_binarySearch(int* nums, int numsSize) {
    int tails[numsSize];
    int size = 0;
    for(int i=0; i<numsSize; i++) {
        int left = 0, right = size;
        while(left < right) {
            int mid = (left+right)/2;
            if(tails[mid] < nums[i]) left = mid+1;
            else right = mid;
        }
        tails[left] = nums[i];
        if(left == size) size++;
    }

    return size;
}

该算法的时间复杂度是O(nlogn)，空间复杂度是O(n)。

三、最长不下降子序列的实际应用

最长不下降子序列在实际应用中有很多使用场景。这里以纸牌游戏为例，介绍一下如何将LIS算法应用到游戏中。

现在有一组扑克牌，每张牌都有一个权重weight，我们将这些牌分为两部分，分别排列成两个序列a和b。每次可以从a或b的顶部取走一张牌，并将该牌放置在一个额外的序列c的顶部。请问当序列a和b遍历完毕后，序列c的最长不下降子序列的长度是多少？

这个问题可以很自然地转化为求解在序列a和b中取出若干个数后，它们的最长不下降子序列的长度。我们将a和b的元素对应相加，得到一个新的序列，然后求新序列的最长不下降子序列长度即可解决问题。

int max(int a, int b) {
    return (a>b) ? a : b;
}

int lengthOfLIS_game(int* a, int aSize, int* b, int bSize) {
    int c[aSize];
    for(int i=0; i<aSize; i++) c[i] = a[i]+b[i];

    int dp[aSize];
    for(int i=0; i<aSize; i++) dp[i] = 1;

    int maxLen = 1;
    for(int i=1; i<aSize; i++) {
        for(int j=0; j<i; j++) {
            if(c[j] < c[i]) {
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
        maxLen = max(maxLen, dp[i]);
    }

    return maxLen;
}

四、结语

本文介绍了最长不下降子序列的定义、求解方法和实际应用。动态规划和二分查找法都是常用的LIS求解方法，它们的时间和空间复杂度有所不同，选择不同的算法取决于具体应用场景。在游戏开发中，LIS算法可以被广泛地应用，为游戏增添了一份趣味和挑战。