如何使用C++中的最长递增子序列算法

王林
王林 原创
2023-09-19 17:21:34 1047浏览

如何使用C++中的最长递增子序列算法

如何使用C++中的最长递增子序列算法,需要具体代码示例

最长递增子序列(Longest Increasing Subsequence,简称LIS)是一个经典的算法问题,其解决思路可以应用于多个领域,如数据处理、图论等。在本文中,我将为大家介绍如何使用C++中的最长递增子序列算法,并提供具体的代码示例。

首先,我们来了解一下最长递增子序列的定义。给定一个序列a1, a2, …, an,我们需要找到一个最长的子序列b1, b2, …, bm,其中b的元素在原序列中的相对顺序是递增的。也就是说,对于任意的i < j,满足aj > ai,那么在b中也有bj > bi。最长递增子序列的长度即为m。

接下来,我们将介绍两种常见的求解最长递增子序列的算法:动态规划算法和贪心算法。

  1. 动态规划算法

动态规划算法将最长递增子序列的求解过程分为多个阶段,并将结果存储在一个二维数组dp中。dp[i]表示以序列中第i个元素结尾的最长递增子序列的长度。

具体求解过程如下:

  • 初始化dp数组的所有元素为1,表示以每个元素结尾的子序列长度至少为1。
  • 从左到右遍历整个序列,对于每个位置i,计算dp[i]的值。
  • 对于每个位置i,遍历其前面位置j,如果aj < ai,则更新dp[i]的值为max(dp[i], dp[j]+1)。

最终的结果为dp数组中的最大值。

下面是用C++实现动态规划算法的代码示例:

#include<iostream>
#include<vector>
using namespace std;

int longestIncreasingSubsequence(vector<int>& nums) {
  int n = nums.size();
  vector<int> dp(n, 1);

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

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

  return res;
}

int main() {
  vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
  int res = longestIncreasingSubsequence(nums);
  cout << "最长递增子序列的长度为:" << res << endl;
  return 0;
}
  1. 贪心算法

贪心算法是一种更加高效的解决最长递增子序列问题的方法。该算法利用一个辅助数组d来保存当前最长递增子序列的末尾元素。遍历整个序列,对于每个元素,使用二分查找的方式确定其在辅助数组d中的位置。

具体求解过程如下:

  • 初始化辅助数组d为一个空数组。
  • 从左到右遍历整个序列,对于每个元素a,如果a大于d的末尾元素,则将a添加到d的末尾。
  • 如果a小于等于d的末尾元素,则使用二分查找的方式找到d中大于等于a的第一个元素,并将其替换为a。

最终的结果为辅助数组d的长度。

下面是用C++实现贪心算法的代码示例:

#include<iostream>
#include<vector>
using namespace std;

int longestIncreasingSubsequence(vector<int>& nums) {
  vector<int> d;

  for (auto num : nums) {
    int left = 0, right = d.size() - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (d[mid] < num) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    if (left >= d.size()) {
      d.push_back(num);
    } else {
      d[left] = num;
    }
  }

  return d.size();
}

int main() {
  vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
  int res = longestIncreasingSubsequence(nums);
  cout << "最长递增子序列的长度为:" << res << endl;
  return 0;
}

以上就是如何使用C++中的最长递增子序列算法的介绍和代码示例。无论是动态规划算法还是贪心算法,都可以在时间复杂度为O(n^2)或O(nlogn)的情况下解决最长递增子序列问题。读者可以根据具体的应用场景选择合适的算法来使用。希望本文能够对大家了解最长递增子序列算法提供帮助。

以上就是如何使用C++中的最长递增子序列算法的详细内容,更多请关注php中文网其它相关文章!

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。