768. Max Chunks To Make Sorted II

惭愧，知道思路居然搞了那么久，中间就是一个数组名字搞错了，搞了半天不对劲。

This question is the same as "Max Chunks to Make Sorted" except the integers of the given array are not necessarily distinct, the input array could be up to length 2000, and the elements could be up to 10**8.

---

Given an array arr of integers (not necessarily distinct), we split the array into some number of "chunks" (partitions), and individually sort each chunk.  After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Input: arr = [5,4,3,2,1]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.

Example 2:

Input: arr = [2,1,3,4,4]
Output: 4
Explanation:
We can split into two chunks, such as [2, 1], [3, 4, 4].
However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.

Note:

• arr will have length in range [1, 2000].
• arr[i] will be an integer in range [0, 10**8].

和 Max Chunks To Make Sorted类似，只不过数字可以重复，而且数字范围为0-10^8,vector的长度为0-2000。

思路：

因为分好块以后，后面块的最小值肯定大于等于前面的最大值。

所以遍历数组，如果arr[i+1]>=max(arr[0],……arr[i])，那么它就可以不与前面i个数划分在一起，否则就必须与前面i个数划分到一个块。再用一个数组a来表示从第一个数到当前数至少划分的块数。所以如果arr[i+1]>=max(arr[0],……arr[i])，那么a[i+1]=a[i]+1,否则就找分界点，使得从j到i+1最小的数大于从0到j-1最大的数，那么j就是一个分界点，在此处a[i+1]=a[j-1]+1，因为分界点可能不只是只有一个，所以取最大的a[i+1]，因此a[i+1]=max(a[i+1],a[j-1]+1)。注意数组下标的范围。

代码：

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int a[2001];
        fill(a,a+2001,1);
        int maxn[2001];
        fill(maxn,maxn+2001,arr[0]);
        for(int i=1;i<arr.size();i++)
        {
            if(arr[i]>maxn[i-1])
                maxn[i]=arr[i];
            else
            {
                maxn[i]=maxn[i-1];
            } 
        }
        for(int i=0;i<arr.size()-1;i++)
        {
            if(arr[i+1]>=maxn[i])
                a[i+1]=a[i]+1;
            else 
            {
                long long minn=arr[i+1];
                for(int j=i;j>0;j--)
                {
                    if(arr[j]<minn)
                        minn=arr[j];
                    if(minn>=maxn[j-1])
                    {
                        a[i+1]=max(a[i+1],a[j-1]+1);
                    }
                }
            }
        }
        return a[arr.size()-1];
    }
};