MathWorks OA 2023 | Count total possible bitonic sequences
Anonymous User
435
MathWorksOnline AssessmentDynamic ProgrammingInterview

So the question was to count total number of bitonic sequences in array.

[1,2,3,2,1], n = 5
Output will be 11

The answer could be very big so we need to print it mod 1e9+7.

The constraint were size of array could be between 1<n<1e5, but the values of the array where 1<n<200.

So the intuition I got was to count all increasing and decreasing subsequences. https://www.geeksforgeeks.org/count-all-increasing-subsequences/

Finally the answer will be incr[i] + decr[i] - 1, but I am not sure how to implement it.

Can someone please help me out ?

Thanks

Here is the code which I had implemented.

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
#define ll long long

ll f(vector<ll> &arr)
{
    int n = arr.size();
    vector<ll> inc(n, 0), dec(n, 0);
    for(int i=1;i<n;i++)
    {
        for(int j=i-1;j>=0;j--)
        {
            if(arr[j] < arr[i])
            {
                inc[i] += inc[j] + 1;
            }
        }
       
    }
    
    for(int i=n-2;i>=0;i--)
    {
        for(int j=i+1; j<n; j++)
        {
            if(arr[j] < arr[i])
            {
                dec[i] += dec[j]+1;
            }
        }
        
        if(dec[i] == 0)
        {
            dec[i]=1;
        }
    }
    
    ll ans = 0;
    for(int i=1;i<n-1;i++)
    {
        ans += (inc[i] * dec[i])%mod;
    }
    return ans;
}

int main()
{
    ll n = 5;
   
    vector<ll> arr = {1,2,3,2,1};
    // for(ll i=0 ;i<n;i++)
    // {
    //     cin>>arr[i];
    // }
    
    cout<<f(arr);
    
    return 0;
}
Comments (1)