本题就是一题LIS（最长递增子序列）的问题。本题要求求最长递增子序列和最长递减子序列。

dp的解法是O(n*n)，这个应该大家都知道。只是本题应该超时了。

由于有O(nlgn）的解法。

可是因为本题的数据特殊性。故此本题能够利用这个特殊性加速到O(n)的解法。当中的底层思想是counting sort分段的思想。就是假设你不会counting sort的话，就非常难想出这样的优化的算法了。

O(nlgn)的利用单调队列性质的解法，利用二分加速是有代表性的，无数据特殊的时候也能够使用。故此这里先给出这个算法代码。

看了代码就知道非常easy的了，只是这里为了更加高效利用代码，就使用了函数指针，代码十分简洁了，刚開始学习的人耐心点看，代码应该非常好的：

#include <stdio.h>

const int MAX_N = 30000;

int arr1[MAX_N], arr2[MAX_N];

inline int max(int a, int b) { return a > b?

a : b; }

inline bool larEqu(int a, int b) { return a <= b; }

inline bool smaEqu(int a, int b) { return a >= b; }

int biSearch(int low, int up, int val, bool (*func)(int , int))

{

	while (low <= up)

	{

		int mid = low + ((up-low)>>1);

		if (func(val, arr2[mid])) low = mid+1;

		else up = mid-1;

	}

	return low;

}

int getLIS(int n, bool (*func)(int, int))

{

	int j = 0;

	arr2[0] = arr1[0];

	for (int i = 1; i < n; i++)

	{

		if (func(arr1[i], arr2[j])) arr2[++j] = arr1[i];

		else arr2[biSearch(0, j, arr1[i], func)] = arr1[i];

	}

	return j+1;

}

int main()

{

	int n;

	while (scanf("%d", &n) != EOF)

	{

		for (int i = 0; i < n; i++)

		{

			scanf("%d", &arr1[i]);

		}

		printf("%d\n", n-max(getLIS(n, larEqu), getLIS(n, smaEqu)));

	}

	return 0;

}

然后是O(n)的时间效率的算法。

就是由于仅仅有1,2,3,这三个数据，故此能够分开窗体。分别记录1。 2， 3 的数据段，在利用上面单调队列的思想的时候，就能够不使用二分法了，而是直接插入就能够了，故此省去了lgn的时间。时间效率就优化到O(n)了。

这个算法卡了我的地方就是下标的问题，老是无法准确记录窗体下标的，故此这里使用个特殊的记录下标的方法。看代码就好像是个O(n*n)的算法。由于循环中有循环。可是大家细致看，事实上这是个O(n)算法。为什么呢？由于循环中的循环总共仅仅是搜索了一遍n个数。无需反复搜索。

#include <stdio.h>

const int MAX_N = 30000;

int arr1[MAX_N], arr2[MAX_N];

inline int max(int a, int b) { return a > b? a : b; }

int getLIS(int n)

{

	int j = 0, one = 0, two = 0;

	arr2[0] = arr1[0];

	for (int i = 1; i < n; i++)

	{

		if (arr1[i] >= arr2[j])

		{

			arr2[++j] = arr1[i];

		}

		else

		{

			if (arr1[i] == 1)

			{

				while (arr2[one] < 2 && one < j) one++;

				arr2[one] = arr1[i];

			}

			else

			{

				while (arr2[two] < 3 && two < j) two++;

				arr2[two] = arr1[i];

			}

		}

	}

	return j+1;

}

int getLDS(int n)

{

	int j = 0, two = 0, thr = 0;

	arr2[0] = arr1[0];

	for (int i = 1; i < n; i++)

	{

		if (arr1[i] <= arr2[j]) arr2[++j] = arr1[i];

		else

		{

			if (arr1[i] == 3)

			{

				while (arr2[thr] > 2 && thr < j) thr++;

				arr2[thr] = arr1[i];

			}

			else

			{

				while (arr2[two] > 1 && two < j) two++;

				arr2[two] = arr1[i];

			}

		}

	}

	return j+1;

}

int main()

{

	int n;

	while (scanf("%d", &n) != EOF)

	{

		for (int i = 0; i < n; i++)

		{

			scanf("%d", &arr1[i]);

		}

		printf("%d\n", n-max(getLIS(n), getLDS(n)));

	}

	return 0;

}