本文共 3190 字，大约阅读时间需要 10 分钟。

最长递增子序列（LIS）分析

1. 基于贪心算法的O(nlogn)方法

最长递增子序列（LIS）的问题可以通过贪心算法在O(nlogn)时间复杂度内解决。这个方法主要基于以下思路：

例子说明

以数组{1,3,5,4,4,8,6,7}为例：

• a[0]=1：LIS长度为1，记录为last[1]=1。
• a[1]=3 >1：LIS长度为2，last[2]=3。
• a[2]=5 >3：LIS长度为3，last[3]=5。
• a[3]=4：可以替换last[3]=5，长度还是3，last[3]=4。
• a[4]=4：无变化。
• a[5]=8 >5：LIS长度为4，last[4]=8。
• a[6]=6：替换last[4]=8，last[4]=6。
• a[7]=7 >6：LIS长度为5，last[5]=7。

最终，LIS长度为5，last数组为{1,3,4,6,7}。

认可队列

通过上述方法，我们可以为每个人记录他的“认可者”（即他前面可以组成LIS的位置）。具体表格如下：

从表格中可以看出，最长队列由7认可的队列构成，队列为{1,3,4,6,7}。

代码实现

#include 
   
    using namespace std;int main() {    int maxn, i;    cin >> maxn;    int a[maxn];    for (i = 0; i < maxn; ++i) {        cin >> a[i];    }    int last[maxn], last_id[maxn], pre[maxn];    int len = 0, maxi;    // 初始化    fill(last.begin(), last.end(), -1);    for (int i = 0; i < maxn; ++i) {        auto pos = lower_bound(last, last + maxn, a[i]);        if (pos != last + maxn) {            int idx = pos - last;            if (len > idx) {                pre[i] = last_id[idx - 1];            } else {                pre[i] = -1;            }            last[idx] = a[i];            last_id[idx] = i;            if (idx > len) {                len = idx;                maxi = i;            }        } else {            if (len == maxn) {                // 不允许，比 Array 过长处理            } else {                *pos = a[i];                last[pos - last] = a[i];                last_id[pos - last] = i;                pre[i] = last_id[pos - last - 1];            }        }    }    int lis[maxn];    for (int i = len - 1; i >= 0; --i) {        lis[i] = a[maxi];        maxi = pre[maxi];    }    cout << "最长公共子串长度：" << len << endl;    for (int i = 0; i < maxn; ++i) {        if (a[i] == lis[0]) {            // 展示过程            break;        }    }    return 0;}
   

2. 动态规划算法

动态规划方法基于以下思想：

• 状态定义：dp[i]记录以第i个元素结尾的最长递增子序列的长度。
• 状态转移：dp[i] = max(dp[j] + 1)，其中j < i且a[j] < a[i]。
• 优化：如果有多个满足条件的j，选择dp[j]最大的那个j。
• 辅助数组：lastidx记录每个ds[i]对应的j值，用于反向追溯最长子序列。

代码示例

#include 
   
    using namespace std;int main() {    int a[6] = {1, 3, 5, 4, 4, 6};    int dp[6], lastidx[6];    for (int i = 0; i < 6; ++i) {        dp[i] = 1;        lastidx[i] = i;        for (int j = 0; j < i; ++j) {            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {                dp[i] = dp[j] + 1;                lastidx[i] = j;            }        }    }    int maxx = 0, maxi = 0;    for (int i = 0; i < 6; ++i) {        if (dp[i] > maxx) {            maxx = dp[i];            maxi = i;        }    }    int lis[6];    for (int i = maxx - 1; i > 0; --i) {        lis[i] = a[maxi];        maxi = lastidx[maxi];    }    cout << "最长公共子串长度：" << maxx << endl;    return 0;}
   

3. 最长公共子序列法

对于给定的数组A，通过以下步骤解决LIS问题：

示例：假设A = {1, 3, 5, 4, 4, 6}，B = {1, 3, 4, 4, 5, 6}，LCS为{1, 3, 4, 4, 6}，去重后得到{1, 3, 4, 6}。

通过上述方法，我们可以在O(NlogN + N2)的时间复杂度内解决LIS问题，并通过动态规划或贪心算法实现优化。这些方法在多种场景下都有广泛的应用。

转载地址：http://vzdyk.baihongyu.com/