C++에서 가장 길게 증가하는 부분 수열의 수

정렬되지 않은 정수 배열이 하나 있다고 가정합니다. 가장 긴 증가하는 부분 수열의 수를 찾아야 하므로 입력이 [1, 3, 5, 4, 7]과 같으면 증가하는 부분 수열이 [1,3,5,7]이므로 출력은 2가 됩니다. [1, 3, 4, 7]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=num 배열의 크기, 크기가 n인 두 개의 배열 len과 cnt를 만들고 값 1로 채웁니다.
• lis :=1
• 1~n
  범위의 i에 대해
  • 0 ~ i – 1 범위의 j에 대해
    • 숫자[i]> 숫자[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]의 최대값
• ans :=0
• 0 ~ n – 1 범위의 i에 대해
  • 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