How to use the longest increasing subsequence algorithm in C++

How to use the Longest Increasing Subsequence algorithm in C requires specific code examples

The Longest Increasing Subsequence (LIS) is a classic Algorithmic problems, the solution ideas can be applied to many fields, such as data processing, graph theory, etc. In this article, I will introduce how to use the longest increasing subsequence algorithm in C and provide specific code examples.

First, let’s understand the definition of the longest increasing subsequence. Given a sequence a1, a2, …, an, we need to find a longest subsequence b1, b2, …, bm, in which the relative order of the elements of b in the original sequence is increasing. That is to say, for any i ai is satisfied, then bj > bi also exists in b. The length of the longest increasing subsequence is m.

Next, we will introduce two common algorithms for solving the longest increasing subsequence: dynamic programming algorithm and greedy algorithm.

1. Dynamic programming algorithm

The dynamic programming algorithm divides the solution process of the longest increasing subsequence into multiple stages and stores the results in a two-dimensional array dp . dp[i] represents the length of the longest increasing subsequence ending with the i-th element in the sequence.

The specific solution process is as follows:

• Initialize all elements of the dp array to 1, which means that the length of the subsequence ending with each element is at least 1.
• Traverse the entire sequence from left to right, and for each position i, calculate the value of dp[i].
• For each position i, traverse its previous position j. If aj

The final result is the maximum value in the dp array.

The following is a code example using C to implement the dynamic programming algorithm:

#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;
}

2. Greedy algorithm

The greedy algorithm is a more efficient way to solve the longest problem Methods for Increasing Subsequence Problems. This algorithm uses an auxiliary array d to save the last element of the current longest increasing subsequence. Traverse the entire sequence, and for each element, use binary search to determine its position in the auxiliary array d.

The specific solution process is as follows:

• Initialize the auxiliary array d as an empty array.
• Traverse the entire sequence from left to right, for each element a, if a is greater than the end element of d, add a to the end of d.
• If a is less than or equal to the last element of d, use binary search to find the first element in d that is greater than or equal to a, and replace it with a.

The final result is the length of the auxiliary array d.

The following is a code example for implementing the greedy algorithm in 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;
}

The above is an introduction and code example of how to use the longest increasing subsequence algorithm in C. Whether it is a dynamic programming algorithm or a greedy algorithm, it can solve the longest increasing subsequence problem with a time complexity of O(n^2) or O(nlogn). Readers can choose the appropriate algorithm to use based on specific application scenarios. I hope this article can help everyone understand the longest increasing subsequence algorithm.

The above is the detailed content of How to use the longest increasing subsequence algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!