一、题目描述

描述：

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学不交换位置就能排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK，则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K) 。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入：

第一行整数 N，表示同学的总数
第二行整数数组，空格隔开，表示 N 位同学身高

输出：

最少需要几位同学出列

样例输入：

1 2	8 186 186 150 200 160 130 197 200

样例输出：

二、最长递增子序列

最长递增子序列（Longest Increasing Subsequence）是指找到一个给定序列的最长子序列的长度，使得子序列中的所有元素单调递增。

例如：{ 3，5，7，1，2，8 } 的 LIS 是 { 3，5，7，8 }，长度为 4。

解法一：转化为求最长公共子序列

其实可以把求最长递增子序列问题转化为求最长公共子序列的问题。

设数组 { 3， 5， 7， 1， 2， 8 } 为 A
对数组 A 排序，排序后的数组为 B = { 1， 2， 3， 5， 7， 8 }。
于是，求数组 A 的最长递增子序列，就是求数组 A 与数组 B 的最长公共子序列。

最长公共子序列的求法见《动态规划DP》。本方法的时间复杂度是

$$Θ(nlgn)+ Θ(n^2) = Θ(n^2)$$

解法二：动态规划法

虽然解法一也是使用动态规划，但是与解法一不同的是，解法二不进行转化，而是直接在原问题上采用动态规划法。

最优子结构：

对于长度为 N 的数组 $A[N] = { a0, a_1, a_2, …, a{n-1}}$，假设我们想求以 $a_i$ 结尾的最大递增子序列长度，设为$L[i]$，那么

$$
L[i] =
\begin{cases}
max(L[j]) + 1, & \text{where $j < i$ and $A[j] < A[i]$} \[2ex]
1, & \text{otherwise}
\end{cases}
$$

也就是 $j$ 的范围是 0 到 $i–1$。这样，想求 $a_i$ 结尾的最大递增子序列的长度，我们就需要遍历 $i$ 之前的所有位置 $j$（0到 i-1），找出$A[j] < A[i]$，计算这些 $j$ 中，能产生最大 $L[j]$ 的 $j$，之后就可以求出 $L[i]$。之后对每一个$A[N]$中的元素都计算以他们各自结尾的最大递增子序列的长度，这些长度的最大值，就是我们要求的问题——数组$A$的最大递增子序列的长度。

重叠子问题：

根据上述推导式采用递归实现的话，有些子问题会被计算很多次。

动态规划法：

综上所述，LIS 问题具有动态规划需要的两个性质，可以使用动态规划求解该问题。设数组 A = { 3，5，7，1，2，8 }，则：

具体的打表方式如下：

初始化对角线为 1；
对每一个 i，遍历 j（0 到 i-1）：
- 若A[i] <= A[j]，置 1。
- 若A[i] > A[j]，取第 j 行的最大值加 1。

打完表以后，最后一行的最大值就是最长递增子序列的长度。由于每次都进行遍历，故时间复杂度还是 $Θ(n^2)$ 。

通常在实现的时候我们不会创建一整个表，因为这样太浪费空间。由打表的过程可知，我们只需要一个一维数组来保存每一行的最大值即可：

// LIS 的动态规划方式实现
#include <iostream>
using namespace std;

int getLISLength(int A[], int len)
{
	/* 一维数组 */
   int* lis = new int[len];  

   /* 初始化为1 */
   for (int i = 0; i < len; ++i) 
      lis[i] = 1;

   /* 计算每个i对应的lis最大值，即打表的过程 */
   for (int i = 1; i < len; ++i)
      for (int j = 0; j < i; ++j)     // 0到i-1
         if ( A[i] > A[j] && lis[i] < lis[j]+1)
            lis[i] = lis[j] + 1;  // 更新

   /* 数组中最大的那个，就是最长递增子序列的长度 */
   int maxlis = 0;
   for (int i = 0; i < len; ++i)
      if ( maxlis < lis[i] )
         maxlis = lis[i];

   delete [] lis;
   return maxlis;
}

int main()
{
  int arr[] = {3, 5, 7, 1, 2, 8};
  cout << getLISLength(arr, 6) << endl;
  return 0;
}

解法三：Θ(nlgn)的方案

本解法的具体操作如下：

开一个栈，依次读取数组元素 x 与栈顶元素 top：
- 如果 x > top，将 x 入栈；
- 如果 x < top，则二分查找栈中第一个大于等于x 的数，并用 x 替换它。

遍历结束之后，最长递增序列长度即为栈的大小。

int getLISLength(int A[], int len)
{
	vector<int> v;  // 模拟栈
	for(int i=0; i<len; ++i)
	{
		if(v.size()==0 || v.back()<A[i])
			v.push_back(A[i]);
		else  // 二分查找
		{
			int mid, low=0, high=v.size()-1;
			while(low<high)
			{
				mid = (low+high)/2;
				if(v[mid] < A[i])
					low = mid + 1;
				else
					high = mid - 1;
			}
			v[low] = A[i];  // 替换
		}
	}
	return v.size();
}

由于使用了二分搜索，故时间复杂度变成了 $Θ(nlgn)$。

特别注意的是：本方法只能用于求最长递增子序列的长度，千万不要以为栈中的序列就是最长递增子序列：

例一：原序列为1，5，8，3，6，7
栈为1，5，8，此时读到3，用3替换5，得到1，3，8；再读6，用6替换8，得到1，3，6；再读7，得到最终栈为1，3，6，7。最长递增子序列为长度4。
例二：原序列为1，5，8，3
则最终栈为1，3，8。明显这不是最长递增子序列！

三、解题报告

根据题意可知，我们需要求出一个“中间点”，使得其左边的【最长递增子序列】和其右边的【最长递减子序列】之和最大。

#include <iostream>
using namespace std;

int main()
{
	int len;
	cin >> len;
	int *A = new int[len];
	for(int i=0; i<len; ++i)
		cin >> A[i];

	// lis[i]表示以A[i]为结尾的最长递增子序列的长度
	int *lis = new int[len];  
	// lds[i]表示以A[i]为起点的最长递减子序列的长度
	int *lds = new int[len];

	for (int i = 0; i < len; ++i) 
	{
		lis[i] = 1;
		lds[i] = 1;
	}

	for(int i=1; i<len; ++i)
		for(int j=0; j<i; ++j)
			if(A[i] > A[j] && lis[i] < lis[j]+1)
				lis[i] = lis[j] + 1;

	for(int i=len-2; i>=0; --i)
		for(int j=len-1; j>i; --j)
			if(A[i] > A[j] && lds[i] < lds[j]+1)
				lds[i] = lds[j] + 1;

	int maxl = 0;
	for(int i=0; i<len; ++i)
		if(maxl < lis[i]+lds[i])
			maxl = lis[i] + lds[i];

	cout << len - maxl + 1 << endl;

	delete [] lis;
	delete [] lds;
	delete [] A;
	return 0;
}