Đếm tất cả các chuỗi con tăng dần trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm số lượng chuỗi ngày càng tăng.

Đối với điều này, chúng tôi sẽ được cung cấp một mảng chứa các chữ số từ 0 đến 9. Nhiệm vụ của chúng tôi là đếm tất cả các chuỗi có trong mảng sao cho phần tử tiếp theo lớn hơn phần tử trước đó.

Ví dụ

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

Đầu ra

14