# Minimum number of deletions to make a sorted sequence

Given an array of **n** integers. Find the minimum number of elements from the array to remove or delete so that when the remaining elements are placed in the same sequence order form a sorted sequence.

**Input:**

First line contains size **N**.

Next line contains **N** input elements for the array

**Output:**

Output the minimum number of deletions to make a sorted sequence.

**Constraints:**

1<= N <=1000
1<= A[i ] <=1000

**Example:**

Input:
5
5 8 5 5 4
Output:
1
Explanation:
The longest increasing subsequence is: (not strictly increasing)
5, 8 or 5,5
So we need to remove minimum three characters
The longest decreasing subsequence is: (not strictly increasing)
8 5 5 4
So we need to remove minimum one character
Thus the final output is 1
And the sorted sequence is the decreasing one
8 5 5 4

So, for the sequence to be sorted we need to check for both the longest increasing and decreasing subsequence.

Let,

Longest increasing subsequence be known as LIS and Longest decreasing subsequence is LDS

So minimum elements to be

deleted= array length- maximum(LIS, LDS)Intuitively, the minimum value of

would be 1 as each element represents the primitive sequence which is either increasing or decreasing one.maximum(LIS, LDS)So, the base value is 1.

Now,

So,

To compute

the recursion function is,LIS(i), LDS(i)As, the base value is 1, for every index

,i,Lis(i)is at least 1.Lds(i)Now, Minimum elements to be deleted =

To go through detailed explanation on LIS go through previous article on LIS: Longest Increasing Subsequence

LDS is quite similar like LIS, follow the recursion for LDS to understand this too.

C++ Implementation:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: