C++에서 증가하는 모든 하위 시퀀스 계산

이 튜토리얼에서는 증가하는 시퀀스의 수를 찾는 프로그램에 대해 논의할 것입니다.

이를 위해 0에서 9까지의 숫자를 포함하는 배열이 제공됩니다. 우리의 임무는 다음 요소가 이전 요소보다 크도록 배열에 있는 모든 시퀀스를 계산하는 것입니다.

예시

#include<bits/stdc++.h>
using namespace std;
//counting the possible subsequences
int count_sequence(int arr[], int n){
   int count[10] = {0};
   //scanning each digit
   for (int i=0; i<n; i++){
      for (int j=arr[i]-1; j>=0; j--)
         count[arr[i]] += count[j];
      count[arr[i]]++;
   }
   //getting all the possible subsequences
   int result = 0;
   for (int i=0; i<10; i++)
      result += count[i];
   return result;
}
int main(){
   int arr[] = {3, 2, 4, 5, 4};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << count_sequence(arr,n);
   return 0;
}

출력

14