牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有 一个长度为n的整数数组A,他现在有一个任务是把数组A分为若干段排序子序列,牛牛想知道他最少可以把这个 数

 

题目：牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有
一个长度为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==序列个数）

int order_count()
{
	int n;//数组大小
	cin >> n;
	vector<int> v;
	(n);//数组大小为n

	//录入数据
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}

	//找波峰波谷(波峰+波谷+1==序列个数，因此ret初始化为1)
	int ret = 1;
	for (int i = 1; i < n - 1; i++)
	{
		//以中间元素和左右两个元素大小作比较，因此i取值最大是n-2
		if ((v[i - 1]<=v[i] && v[i]>=v[i + 1]) || (v[i - 1] >= v[i] && v[i] <= v[i + 1]))
		{
			ret++;//每进来一次说明有一个波峰/波谷
			//正常情况下，i-1,i,i+1位置都判断过来了，应该判断i+2位置了，
			//此时是i的位置，则需要i加1一次，循环上去i再加一次，就是i+2了，
			//但是由于i的最大取值是i-2,因此当i==n-3时，如果i加1一次是n-2,
			//循环上去再加一次1就是n-1,越界了，因此当i==n-3时无需再加1
			if (i != n - 3)
			{
				i++;
			}
		}
	}
	return ret;
}