จำนวนลำดับที่ยาวที่สุดใน C++

สมมุติว่าเรามีอาร์เรย์ของจำนวนเต็มที่ไม่เรียงลำดับ เราต้องหาจำนวนลำดับการเพิ่มขึ้นที่ยาวที่สุด ดังนั้นหากอินพุตเป็นเช่น [1, 3, 5, 4, 7] ผลลัพธ์จะเป็น 2 เนื่องจากลำดับย่อยที่เพิ่มขึ้นคือ [1,3,5,7] และ [1, 3, 4, 7]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของอาร์เรย์ num สร้างสองอาร์เรย์ len และ cnt ของขนาด n แล้วเติมด้วยค่า 1
• ลิส :=1
• สำหรับฉันอยู่ในช่วง 1 ถึง n
  • สำหรับ j ในช่วง 0 ถึง i – 1
    • ถ้า nums[i]> nums[j] แล้ว
      • ถ้า len[j] + 1> len[i] แล้ว len[i] :=len[j] + 1 และ cnt[i] :=cnt[j]
      • มิฉะนั้น เมื่อ len[j] + 1 =len[j] แล้ว cnt[i] :=cnt[i] + cnt[j]
    • lis :=สูงสุดของ lis และ len[j]
• ตอบ :=0
• สำหรับ i ในช่วง 0 ถึง n – 1
  • ถ้า len[i] =lis แล้ว ans :=ans + cnt[j]
• คืนสินค้า

ตัวอย่าง(C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int findNumberOfLIS(vector<int>& nums) {
      int n = nums.size();
      vector <int> len(n, 1), cnt(n, 1);
      int lis = 1;
      for(int i = 1; i < n; i++){
         for(int j = 0; j < i; j++){
            if(nums[i] > nums[j]){
               if(len[j] + 1 > len[i]){
                  len[i] = len[j] + 1;
                  cnt[i] = cnt[j];
               }
               else if(len[j] + 1 == len[i]){
                  cnt[i] += cnt[j];
               }
            }
            lis = max(lis, len[i]);
         }
      }
      int ans = 0;
      for(int i = 0; i < n; i++){
         if(len[i] == lis)ans += cnt[i];
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,3,5,4,7};
   cout << (ob.findNumberOfLIS(v));
}

อินพุต

[1,3,5,4,7]

ผลลัพธ์

2