解题思路

题意：给定一组正整数，允许把数组切成若干连续的“块”，对每一块单独排序后再按原顺序拼接，要求拼接后的整个数组是从小到大有序，问最多能切成多少块。

核心想法：

• 设在位置 i 后面切一刀（左边是 0..i 这一块，右边是 i+1..n-1）。
• 若想切在这里合法，那么左边块里最大的数一定不能大于右边所有数中最小的数，否则排序后左块仍会有元素比右块大，拼接后整体不会有序。
• 因此，切分条件是：

题目内容

两队学生拿着号码牌，排成 $1$ 队，选择队伍中连续的几个学生将他们按照号码牌就地 升序 排序之后连接起来，使得连接的结果和直接整体按升序排列后的结果一致

输入描述

一组正整数数组

如：$5$ $4$ $3$ $2$ $1$，数组长度为【$1,500$】

输出描述

最多将学生分成多少块

样例1

输入

2 1 3 4 4 5

输出

5

说明

分成 $[2,1],[3],[4],[4],[5]$ 可以得到最多的块数。

样例2

输入

5 4 3 2 1

输出

1

说明

将数组分成 $2$ 块或者更多块，都无法得到所需的结果。

例如，分成 $[5,4],[3,2,1]$ 的结果是 $[4, 5,1,2,3]$，这不是有序的数组。