初夏小谈： NC：排序子序列问题

问题：

1. 牛牛定义排序子序列为一个数组中一段连续的子序列, 并且这段子序列是非递增或者非递减排序的。牛牛有
一个长度为n的整数数组A, 他现在有一个任务是把数组A分为若干段排序子序列, 牛牛想知道他最少可以把这个
数组分为几段排序子序列.
如样例所示, 牛牛可以把数组A划分为[1, 2, 3]和[2, 2, 1]两个排序子序列, 至少需要划分为2个排序子序列, 所以输出
2
输入描述：
输入的第一行为一个正整数n(1 ≤ n ≤ 10 ^ 5)
第二行包括n个整数A_i(1 ≤ A_i ≤ 10 ^ 9), 表示数组A的每个数字。
输出描述：
输出一个整数表示牛牛可以将A最少划分为多少段排序子序列
示例1 :
输入
6
1 2 3 2 2 1
输出
2

该题目意思就是在一个数组中找出最少的有序子序列数量。

这个题的思路是：

  （1）、由于找有序子序列的数量，所以他们的特点就是在这一子序列中全部都是递增或者递减的。，由此我们只要找到极大值或者极小值就能解决此问题。

  （2）、极大值和极小值是通过正余弦函数图像来类比过来的。因为相邻的极值之间不是递增就是递减的。

  （3）、最后找到极值的数量+1就是，求解的答案。为什么+1呢，想一想如果有一个极值的话是不是一段子序列是递增的，一段子序列是递减的。就是两端有序子序列。

特殊情况：

1. 有可能在极值处不是一个值而是好几个值，它们都一样大，这样将如何解决？
2. 有可能在开始就许多相等的数据，如何处理？
3. 假如极值之间再也没有数据的话，那么子序列数量就不会像之前那样计算

解决办法：

   解决1：针对问题一，

              第一步：可以标记第一个相等数据的位置继续往后找最后一个相等的数据并且再次标记。然后再用标记的最后一个来进行比较就OK了。数据都一样大，之后在进行比较。

   解决2：

              开始时，如果数据重复就一直往下走，标记最后一个数据，再进行比较。为判断是否为极大值/极小值做铺垫。

   解决3：

              在判断相邻极值之间是否有数据时，要用标记极大值的第一个数据坐标减去极小值的最后一个标记数据的坐标是否为1，或者标记极大值的最后一个数据坐标减标记极小值的第一个数据的坐标是否为-1.为1/-1就说明极值间没有数据。此时就注意如果遇到两次极值间都没有数据就需要将子序列数减一。

特殊序列图：

代码实现：

#include<iostream>
#include<vector>
using namespace std;

int DisposeData(vector<int>& V)
{
	int MaxFirstEqual = 0;
	int MaxLastEqual = 0;
	int MinFirstEqual = 0;
	int MinLastEqual = 0;
	int flag = 0;
	//记录开始等位置
	int equal = 0;
	//记录最少可以分割的子序列数
	int num = 0;
	//判断极值出现位置
	for (size_t i = 1; i < V.size() - 1; i++)
	{
		//如果数据相同就一直往后走。
		while (V[i] == V[i - 1])
		{
			i++;
			if (i >= V.size())
			{
				return 1;
			}
		}
		//两种特殊情况
		//如果当前数据大于前面数据，而后面有一部分等于当前数据，
		if (V[i] > V[i - 1] && V[i] == V[i + 1])
		{
			MaxFirstEqual = i;
			while (V[i] == V[i + 1])
			{
				i++;
				if (i >= V.size() - 1)
				{
					break;
				}

			}
			//如果走完相等的数据，当前数据大于后面第一个数据说明是极大值
			if (i < V.size() - 1)
			{
				if (V[i] > V[i + 1])
				{
					MaxLastEqual = i;
					num++;
				}
			}
		}
		//如果当前数据小于前面数据，而后面有一部分等于当前数据，
		if (V[i] < V[i - 1] && V[i] == V[i + 1])
		{
			MinFirstEqual = i;
			while (V[i] == V[i + 1])
			{
				i++;
				if (i >= V.size() - 1)
				{
					break;
				}

			}
			//如果走完相等的数据，当前数据小于后面第一个数据说明是极大值
			if (i < V.size() - 1)
			{
				if (V[i] < V[i + 1])
				{
					MinLastEqual = i;
					num++;
				}
			}
		}
		//极小值
		if (V[i] < V[i - 1] && V[i] < V[i + 1])
		{
			MinFirstEqual = MinLastEqual = i;
			num++;
		}
		//极大值
		if (V[i] > V[i - 1] && V[i] > V[i + 1])
		{
			MaxFirstEqual = MaxLastEqual = i;
			num++;
		}
		//判断极值之间有没有数据
		//每两次num--；
		if (MaxFirstEqual - MinLastEqual == 1 || MaxLastEqual - MinFirstEqual == -1)
		{
			flag++;
			if (flag % 2 == 0)
			{
				num--;
			}
		}
	}
	//极值数量加1就是分割的数据数。
	num++;
	return num;
}
int main()
{
	//数组大小
	int count = 0;
	vector<int> v;
	cout << "请输入所要的数据个数:";
	cin >> count;
	cout << "请输入" << count << "个数据:";
	v.resize(count, 0);
	for (int i = 0; i < count; i++)
	{
		cin >> v[i];
	}
	int num = DisposeData(v);
	cout << "num = " << num << endl;
	system("pause");
	return 0;
}

运行结果：

运行特殊情况：

特别注意：

              1.在极值有多个相等的数据时，在往下走遇到最后一个极值，判断下一个的大小时应当注意是否越界。否则程序崩溃。我在里面踩坑滋味哈哈。

                                                                                                                                                              珍&源码