Cara menggunakan algoritma urutan terpanjang yang meningkat dalam C++

Cara menggunakan algoritma Susunan Bertambah Terpanjang dalam C++ memerlukan contoh kod khusus

Susulan Bertambah Terpanjang (LIS) ialah masalah algoritma klasik, dan idea penyelesaiannya boleh digunakan pada berbilang Medan seperti pemprosesan data, teori graf , dsb. Dalam artikel ini, saya akan memperkenalkan cara menggunakan algoritma urutan terpanjang yang meningkat dalam C++ dan memberikan contoh kod khusus.

Pertama, mari kita fahami takrifan susulan yang paling lama meningkat. Diberi jujukan a1, a2, …, an, kita perlu mencari jujukan terpanjang b1, b2, …, bm, di mana susunan relatif unsur-unsur b dalam jujukan asal semakin meningkat. Maksudnya, untuk mana-mana i < j, jika aj > Panjang susulan bertambah terpanjang ialah m.

Seterusnya, kami akan memperkenalkan dua algoritma biasa untuk menyelesaikan urutan yang paling lama meningkat: algoritma pengaturcaraan dinamik dan algoritma tamak.

1. Algoritma Pengaturcaraan Dinamik

Algoritma pengaturcaraan dinamik membahagikan proses penyelesaian bagi jujukan yang paling lama meningkat kepada berbilang peringkat dan menyimpan keputusan dalam dp tatasusunan dua dimensi. dp[i] mewakili panjang jujukan peningkatan terpanjang yang berakhir dengan unsur ke-i dalam jujukan.

Proses penyelesaian khusus adalah seperti berikut:

• Mulakan semua elemen tatasusunan dp kepada 1, yang bermaksud panjang urutan yang berakhir dengan setiap elemen ialah sekurang-kurangnya 1.
• Lintas keseluruhan jujukan dari kiri ke kanan, dan untuk setiap kedudukan i, hitung nilai dp[i].
• Untuk setiap kedudukan i, lalui kedudukan sebelumnya j Jika aj

Hasil akhir ialah nilai maksimum dalam tatasusunan dp.

Berikut ialah contoh kod untuk melaksanakan algoritma pengaturcaraan dinamik dalam 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;
}

2. Algoritma tamak

Algoritma tamak ialah cara yang lebih cekap untuk menyelesaikan masalah susulan yang semakin lama semakin meningkat. Algoritma ini menggunakan tatasusunan tambahan d untuk menyimpan elemen terakhir bagi urutan terpanjang yang semakin meningkat semasa. Lintas keseluruhan jujukan, dan untuk setiap elemen, gunakan carian binari untuk menentukan kedudukannya dalam tatasusunan tambahan d.

Proses penyelesaian khusus adalah seperti berikut:

• Memulakan tatasusunan tambahan d sebagai tatasusunan kosong.
• Lintas keseluruhan jujukan dari kiri ke kanan, untuk setiap elemen a, jika a lebih besar daripada elemen akhir d, tambahkan a pada hujung d.
• Jika a kurang daripada atau sama dengan elemen terakhir d, gunakan carian binari untuk mencari elemen pertama dalam d yang lebih besar daripada atau sama dengan a, dan gantikan dengan a.

Hasil akhir ialah panjang tatasusunan tambahan d.

Berikut ialah contoh kod untuk melaksanakan algoritma tamak dalam 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;
}

Di atas ialah pengenalan dan contoh kod tentang cara menggunakan algoritma urutan yang paling lama meningkat dalam C++. Sama ada algoritma pengaturcaraan dinamik atau algoritma tamak, ia boleh menyelesaikan masalah urutan terpanjang yang semakin meningkat dengan kerumitan masa O(n^2) atau O(nlogn). Pembaca boleh memilih algoritma yang sesuai untuk digunakan berdasarkan senario aplikasi tertentu. Saya harap artikel ini dapat membantu semua orang memahami algoritma urutan yang semakin lama semakin meningkat.

Atas ialah kandungan terperinci Cara menggunakan algoritma urutan terpanjang yang meningkat dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!