Minimum number of elements which are not part of Increasing or decreasing subsequence in array

Minimum number of elements which are not part of Increasing or decreasing subsequence in array

The idea is to make a decision on each index, starting from index 0, one by one. For each index there can be three possibilities, first, it can belong to increasing sequence, second, it can belong to decreasing sequence, third, it does not belong to any of these sequences.
So, for each index, check for the optimal answer (minimum element which is not part of any of the subsequences) by considering it once as a part of increasing subsequence or as a part of decreasing subsequence. If the optimal answer cannot be achieved by them then leave it as the element which is not part of any of the sequence.

To decrease the complexity (using Dynamic Programming), we can store the number of elements which are not part of any of the subsequences using 3D array dp[x][y][z], where x indicates the decision index, y indicates the last index of decreasing sequence, z indicates the last index of increasing sequence.

a = Find length of LIS from left to right, also store indexes of LIS.

b = Find length of LIS from right to left, consider only those indices which are not part of LIS from left to right.

ans = n -(a+b)

Input : arr[] = { 7, 8, 1, 2, 4, 6, 3, 5, 2, 1, 8, 7 }
Output : 2
Increasing sequence can be { 1, 2, 4, 5, 8 }.
Decreasing sequence can be { 7, 6, 3, 2, 1 }.
So, only 2 (8, 7) element is left which are not part of
either of the subsequences.

Input : arr[] = { 1, 4, 2, 3, 3, 2, 4, 1 }
Output : 0
Increasing sequence can be { 1, 2, 3, 4 }.
Decreasing sequence can be { 4, 3, 2, 1 }.
So, no element is left which is not part of either of
the subsequences.

#include<bits/stdc++.h>
using namespace std;
int dp[103][103][103];

int func(vector<int>& ar, int i, int inc, int dec, int h)
{
if(i>h)return 0;

int ans=INT_MAX;
if(dp[i][inc][dec]!=-1)return dp[i][inc][dec];
if(ar[inc]<ar[i])
{
ans = min(ans,min(func(ar,i+1,i,dec,h),1+func(ar,i+1,inc,dec,h) ) );
}
if(ar[dec]>ar[i])
{
ans = min(ans,min(func(ar,i+1,inc,i,h),1+func(ar,i+1,inc,dec,h) ) );
}
if(ar[inc]>=ar[i] and ar[dec]<=ar[i] )
{
ans = min(ans,1+func(ar,i+1,inc,dec,h));
}
dp[i][inc][dec]= ans;
return ans;


}

int main()
{
int t;
cin>>t;
while(t--)
{
for(int i=0;i<103;i++)
{
for(int j=0;j<103;j++)
{
for(int k=0;k<103;k++)
{
dp[i][j][k]=-1;
}
}
}
int n;
cin>>n;
vector<int> ar(n+2);
ar[0]=INT_MAX;
ar[1]=INT_MIN;
for(int i=2;i<n+2;i++)
{
cin>>ar[i];
}

cout<<func(ar,2,1,0,n+1)<<endl;

}
return 0;

}