數組排序最小復雜度

Problem statement:

問題陳述：

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.

給定n個整數數組。 從數組中查找要刪除或刪除的最小元素數，以便在其余元素以相同順序放置時形成排序的序列。

Input:

輸入：

First line contains size N.
Next line contains N input elements for the array

第一行包含大小N。
下一行包含該數組的N個輸入元素

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 

Solution Approach:

解決方法：

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

最長的遞增子序列稱為LIS，最長的遞減子序列為LDS

So minimum elements to be deleted= array length- maximum(LIS, LDS)

因此要刪除的最小元素=數組長度-最大(LIS，LDS)

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

直觀地， 最大值(LIS，LDS)的最小值為1，因為每個元素代表原始序列，原始序列要么遞增要么遞減。

So, the base value is 1.

因此，基準值為1。

Now,

現在，

Lis(i)=longest increasing subsequence starting from index 0 to index i
Lds(i)=longest decreasing subsequence starting from index 0 to index i 

So,

所以，

To compute LIS(i), LDS(i) the recursion function is,

為了計算LIS(i)，LDS(i) ，遞歸函數為

As, the base value is 1, for every index i, Lis(i), Lds(i) is at least 1.

這樣，對于每個索引i ，基值是1， Lis(i) ， Lds(i)至少為1。

1)  Create two DP array, Lis[n],Lds[n]
2)  Initialize both the DP array with 1.
for i=0 to n-1
Lis[i]=1,Lds[i]=1;
3)  Now, to compute the Lis[i],Lds[i]
for index  i=1 to n-1         
for previous index j=0 to i-1
//if (arr[i],arr[j]) is inceasing sequence
if(lis[i]<lis[j]+1 &&a[i]≥a[j])
lis[i]=lis[j]+1;
//if (arr[i],arr[j]) is deceasing sequence
if(lds[i]<lds[j]+1 &&a[i]≤a[j])
lds[i]=lds[j]+1;
end for
end for 

Now, Minimum elements to be deleted =

現在，要刪除的最少元素=

n-maximum(maximum value in (lds),maximum value in (lis))

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

要詳細了解LIS，請閱讀上一篇有關LIS： 最長遞增子序列的文章。

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

LDS與LIS十分相似，也遵循LDS的遞歸來理解這一點。

C++ Implementation:

C ++實現：

#include <bits/stdc++.h>
using namespace std;
int LIDS(vector<int> arr, int n)
{
int LIS[n], LDS[n];
for (int i = 0; i < n; i++)
LIS[i] = 1;
for (int i = 0; i < n; i++)
LDS[i] = 1;
int maxi = INT_MIN, maxd = INT_MIN;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
// for longest increasing sequence
if (arr[i] >= arr[j] && LIS[i] < LIS[j] + 1)
LIS[i] = LIS[j] + 1;
// for longest decreasing sequence
if (arr[i] <= arr[j] && LDS[i] < LDS[j] + 1)
LDS[i] = LDS[j] + 1;
}
//find maximum longest s orted sequence
if (LIS[i] > maxi)
maxi = LIS[i];
if (LDS[i] > maxd)
maxd = LDS[i];
}
return std::max(maxi, maxd);
}
int main()
{
int t, n, item;
cout << "Enter n:\n";
scanf("%d", &n);
cout << "Enter the array\n";
vector<int> a;
for (int j = 0; j < n; j++) {
scanf("%d", &item);
a.push_back(item);
}
cout << "Minimum elements needed to be deleted to create sorted sequence: " << n - LIDS(a, n) << endl;
return 0;
}

Output:

輸出：

Enter n:
5
Enter the array
5 8 5 5 4
Minimum elements needed to be deleted to create sorted sequence: 1

翻譯自: https://www.includehelp.com/icp/minimum-number-of-deletions-to-make-a-sorted-sequence.aspx

數組排序最小復雜度