Count all increasing subsequences in C++

In this tutorial, we will be discussing a program to find the number of increasing sequences.

For this we will be provided with an array containing digits 0 to 9. Our task is to count all the sequences present in the array such that the next element is greater than the previous element.

Example

 Live Demo

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

Output

14