C++ || O(n^2) || Recursion ||  Memoization Solution || DP
We will consider every element as starting element than call the recursive function.\nSince its the first element we have not decided that will it be increasing
We will consider every element as starting element than call the recursive function.\nSince its the first element we have not decided that will it be increasing or decreasing sequence.\nSo,\n1. state=0  :-means we have not decided is it a increasing or decreasing we will consider both conditions\n```\n  if(ele<rating[i]) ans+=solve(i,taken+1,1,rating);\n  else if(ele>rating[i]) ans+=solve(i,taken+1,2,rating);\n```\n\n2. state=1 :- mean it increasing sequence and we have to search element greater than the current.\n```\n  if(ele<rating[i]) ans+=solve(i,taken+1,1,rating);\n```\n3. state=2 :- means its a decreasing sequence and we have to search element less than the current\n ```\n    if(ele>rating[i]) ans+=solve(i,taken+1,2,rating);\n```\ntaken :- the number of element we have taken in the sequence.\n\nSo the Complexity is O(n*(n*(3*(4)))=> O(n^2).\n```\nclass Solution {\npublic:\n    int dp[1001][4][3];\n    int solve(int idx,int taken,int state,vector<int> &rating){\n        int n=rating.size();\n        if(taken==3) return 1;\n        if(dp[idx][taken][state]!=-1) return dp[idx][taken][state];\n        \n        int ans=0,ele=rating[idx];\n        for(int i=idx+1;i<n;i++){\n            if(state==0){\n                if(ele<rating[i]) ans+=solve(i,taken+1,1,rating);\n                else if(ele>rating[i]) ans+=solve(i,taken+1,2,rating);\n            }\n            else if(state==1){\n                if(ele<rating[i]) ans+=solve(i,taken+1,1,rating);\n            }\n            else if(state==2){\n                if(ele>rating[i]) ans+=solve(i,taken+1,2,rating);\n            }\n        }\n        return dp[idx][taken][state]=ans;\n    }\n    int numTeams(vector<int>& rating) {\n        int ans=0,n=rating.size();\n        memset(dp,-1,sizeof(dp));\n        \n        for(int i=0;i<=n-3;i++){\n            ans+=solve(i,1,0,rating);\n        }\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C']