C++实现最长下降子序列的算法 |21xrx.com

C++实现最长下降子序列的算法

2023-07-06 05:45:15 深夜i -- --

C++ 最长下降子序列算法

最长下降子序列是指一个序列中连续的子序列严格单调递减，而其中元素可以随意重复。在计算机科学中，求解最长下降子序列的问题是非常常见和重要的一类问题。本文将介绍使用C++实现最长下降子序列的算法。

算法思路：

此算法可以使用动态规划来解决。动态规划的思路是，在每个位置上，找到一个最大的递减长度。如果一个数比前面所有数都小，那么我们将它的递减长度设置为1。如果这个数沿着前面的值递减，那么我们的递减序列长度就是前面元素的递减序列长度+1。

首先，我们将所有元素的递减序列长度都设置为1，然后从第二个元素开始遍历，比较当前元素与前面元素的大小，如果当前元素小于前面元素，那么更新当前元素的递减序列长度为前面元素的递减序列长度+1，否则保持原有长度不变。

在所有元素的递减序列长度求解完毕后，我们可以通过遍历这些长度来找到最长的递减序列长度。最终，我们可以从记录中推导出最长下降子序列本身。具体来说，我们可以从最长下降子序列的最后一个元素开始，逆向遍历记录，沿着元素长度递减的方向查找最长下降子序列。

代码实现：

下面是C++代码实现最长下降子序列的算法。为了方便起见，我们假定原始序列是一个整数数组，用n来表示数组的长度。max_length存储最长下降子序列的长度，lengths数组保存每个元素的递减序列长度，而path数组用于记录每个元素的最长递减路径。


#include <iostream>
#include <vector>
using namespace std;
vector<int> getLongestDownSubsequence(int arr[], int n) {
  int max_length = 0, max_index = 0;
  int lengths[n], path[n];
  for (int i = 0; i < n; i++) {
    lengths[i] = 1;
    path[i] = -1;
    for (int j = 0; j < i; j++) {
      if (arr[j] > arr[i]) {
        if (lengths[j] + 1 > lengths[i]) {
          lengths[i] = lengths[j] + 1;
          path[i] = j;
        }
      }
    }
    if (lengths[i] > max_length) {
      max_length = lengths[i];
      max_index = i;
    }
  }
  vector<int> subsequence;
  for (int i = max_index; i != -1; i = path[i]) {
    subsequence.push_back(arr[i]);
  }
  return subsequence;
}
int main() {
  int arr[] = 2;
  int n = sizeof(arr) / sizeof(arr[0]);
  vector<int> subsequence = getLongestDownSubsequence(arr, n);
  cout << "最长下降子序列长度为：" << subsequence.size() << endl;
  cout << "最长下降子序列为：";
  for (int i = subsequence.size() - 1; i >= 0; i--) {
    cout << subsequence[i] << " ";
  }
  cout << endl;
  return 0;
}

输出结果：

最长下降子序列长度为：4

最长下降子序列为：9 5 4 3

总结：

本文介绍了使用C++实现最长下降子序列的算法。该算法使用了动态规划的思想，将序列中的每个元素的递减长度通过记录的方式求解出来，然后遍历这些长度，找到最长的递减序列长度。最后，通过遍历记录，可以推导出最长下降子序列本身。

上一篇: idea打包java可执行jar包

下一篇: C++单目三维重建代码

评论区

()

相似文章