最多能完成排序的块证明

题目

今天中午我表达自己的想法时， 好像 没讲清楚，现在补充一下吧

实现

先重新叙述一遍郭老师的方法（拿样例举例）

样例

5 2 1 3 4 4

1.将数组排序

1 2 3 4 4

2.标记出每个数排好序后的下标

原值2 1 3 4 4 下标2 1 3 4 4

3.i从1~n枚举，_max = max(a[j])(1 <= j <= i)，当_max == i时，就可以多划分一个块

证明

记排好序后的数组为b

记a[i]对应的b数组中的数为b[j](即a[i] == b[j])

则为了让a[i]移动到第j个位置，最少也要将(i ~ j)划为一个块

而(i~j)中的数也得满足要求(即Ta们所对应的b[j]也得在(i ~ j)中)，

1.满足要求

就将Ta们划分成一个块

2.不满足要求

为了满足Ta们的要求，范围会再次扩大，而扩大后的范围中的数又要再次判断(递归)

重点来了

看似要写成递归了，可是我们会发现，这个块的左端点是固定的 (读者自证不难)， 所以我们只用找到这个块的目前的右端点(即目前(i, j)中每一个点，所最大的对应的b数组的下标)，当i走到这个右端点时，则说明满足要求了。(因为每一个数所要求的范围一定在左端点和右端点之间，而i和右端点重合，则表明在左端点到i的数中在要求的范围里面)