All problems

Max Chunks To Make Sorted II

Hard · monotonic-stack

You are given a list of integers arr. Values may repeat.

Cut the list into one or more chunks: neighbouring runs of elements that together cover the whole list, in order, without overlapping. Then sort each chunk on its own, from smallest to largest, and join the chunks back together in their original order.

A way of cutting is good if the joined result is the whole list sorted from smallest to largest. Return the largest number of chunks in any good way of cutting.

Examples

Example 1

Input: arr = [2, 1, 3, 4, 4]

Output: 4

Cut into [2, 1], [3], [4], [4]. Sorting the first chunk gives [1, 2], and the joined list is 1, 2, 3, 4, 4, which is sorted. Four chunks is the most possible.

Example 2

Input: arr = [5, 4, 3, 2, 1]

Output: 1

Any cut would leave a large value in an earlier chunk than a smaller one, so the list has to stay in one chunk.

Example 3

Input: arr = [1, 1, 1]

Output: 3

Equal values can be separated freely: [1], [1], [1] joins to a sorted list.

Constraints