如何用动态规划解决可前后追加元素的最长递减子序列问题？

问题规则 #

• 若元素大于序列首元素，可追加至序列前端；
• 若元素小于序列尾元素，可追加至序列后端；
• 可选择忽略元素（这是问题的核心难点）。

示例 #

输入：{6, 7, 3, 5, 4}
最长序列构建过程：

1. 初始序列为{6}；
2. 7大于6，追加至前端得到{7, 6}；
3. 忽略3；
4. 5小于6，追加至后端得到{7, 6, 5}；
5. 4小于5，追加至后端得到{7, 6, 5, 4}。

若追加3，序列会变为{7, 6, 3}，后续无法追加4，长度更短。

你的错误原因 #

你改编的LIS算法只记录了以第i个元素结尾的序列长度，但没有跟踪序列的首元素和尾元素——这两个值是决定后续元素能否追加的关键，仅存长度无法覆盖所有可能的序列扩展情况，所以结果错误。

错误代码：

int adapted_LIS(int input[], int n)
{
    int score[n] = {};
    score[0] = 1;
    for (int i = 1; i < n; i++)
    {
        score[i] = 1;
        int front = input[i];
        int back = input[i];
        for (int j = 0; j < i; j++)
        {
            if (input[j] > front)
            {
                front = input[j];
                score[i] = std::max(score[i], score[j] + 1);
            }
            else if (input[j] < back)
            {
                back = input[j];
                score[i] = std::max(score[i], score[j] + 1);
            }
        }
    }
    return *std::max_element(score, score + n);
}

正确的动态规划解法 #

核心思路 #

我们需要跟踪每个可能序列的首元素、尾元素和长度，并针对每个新元素，尝试三种操作：单独成序列、接在已有序列前端、接在已有序列后端。为了优化空间和效率，我们用两个哈希表维护最优序列：

• head_map：键为序列首元素，值为(最小尾元素, 最长长度)——相同首元素下，尾元素越小越容易后续追加更小的元素；
• tail_map：键为序列尾元素，值为(最大首元素, 最长长度)——相同尾元素下，首元素越大越容易后续追加更大的元素。

代码实现 #

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <vector>

int longestSequence(std::vector<int>& input) {
    if (input.empty()) return 0;
    
    // head_map: key=首元素h, value=(最小尾元素t, 最长长度)
    std::unordered_map<int, std::pair<int, int>> head_map;
    // tail_map: key=尾元素t, value=(最大首元素h, 最长长度)
    std::unordered_map<int, std::pair<int, int>> tail_map;
    int max_len = 0;
    
    for (int num : input) {
        int current_len = 1;
        int best_h = num;
        int best_t = num;
        
        // 尝试接在已有序列的后端：找所有尾元素>num的序列，取最长的那个扩展
        int max_back_len = 0;
        int best_back_h = num;
        for (auto& entry : tail_map) {
            int t = entry.first;
            auto& [h, len] = entry.second;
            if (t > num && len > max_back_len) {
                max_back_len = len;
                best_back_h = h;
            }
        }
        if (max_back_len + 1 > current_len) {
            current_len = max_back_len + 1;
            best_h = best_back_h;
            best_t = num;
        }
        
        // </think_never_used_51bce0c785ca2f68081bfa7d91973934>尝试接在已有序列的前端：找所有首元素<num的序列，取最长的那个扩展
        int max_front_len = 0;
        int best_front_t = num;
        for (auto& entry : head_map) {
            int h = entry.first;
            auto& [t, len] = entry.second;
            if (h < num && len > max_front_len) {
                max_front_len = len;
                best_front_t = t;
            }
        }
        if (max_front_len + 1 > current_len) {
            current_len = max_front_len + 1;
            best_h = num;
            best_t = best_front_t;
        }
        
        // 更新head_map：保留相同首元素下的最优序列
        if (head_map.find(best_h) == head_map.end()) {
            head_map[best_h] = {best_t, current_len};
        } else {
            auto& [existing_t, existing_len] = head_map[best_h];
            if (current_len > existing_len || (current_len == existing_len && best_t < existing_t)) {
                head_map[best_h] = {best_t, current_len};
            }
        }
        
        // 更新tail_map：保留相同尾元素下的最优序列
        if (tail_map.find(best_t) == tail_map.end()) {
            tail_map[best_t] = {best_h, current_len};
        } else {
            auto& [existing_h, existing_len] = tail_map[best_t];
            if (current_len > existing_len || (current_len == existing_len && best_h > existing_h)) {
                tail_map[best_t] = {best_h, current_len};
            }
        }
        
        // 更新全局最长长度
        if (current_len > max_len) {
            max_len = current_len;
        }
    }
    
    return max_len;
}

int main() {
    std::vector<int> input = {6,7,3,5,4};
    std::cout << longestSequence(input) << std::endl; // 输出4
    return 0;
}

代码说明 #

1. 遍历每个元素时，先尝试将其接在符合条件的已有序列前端或后端，计算可能的最长长度；
2. 更新哈希表时，优先保留长度更长的序列，长度相同时保留更利于后续扩展的序列（首元素更大/尾元素更小）；
3. 最终全局最长长度就是问题的答案。

内容的提问来源于stack exchange，提问作者Gabriel Henrique