问题：

给定数组，切分为left和right，使得left的所有元素<=right的所有元素，返回left的长度

Example 1:
Input: [5,0,3,8,6]
Output: 3
Explanation: left = [5,0,3], right = [8,6]

Example 2:
Input: [1,1,1,0,6,12]
Output: 4
Explanation: left = [1,1,1,0], right = [6,12]
 

Note:
2 <= A.length <= 30000
0 <= A[i] <= 10^6
It is guaranteed there is at least one way to partition A as described.

　　

解法：

遍历数组，记录left的最大值maxleft

若遍历到的A[i]<maxleft，那么left数组要扩张到A[i]，

这时候maxleft也要更新到A[0]~A[i]的最大值maxnow。

代码参考：

 1 class Solution {
 2 public:
 3     int partitionDisjoint(vector<int>& A) {
 4         int maxleft=A[0], maxnow=A[0], res=0;
 5         for(int i=1; i<A.size(); i++){
 6             if(A[i]<maxleft) {
 7                 res=i;
 8                 maxleft=maxnow;
 9             }else{
10                 maxnow=max(maxnow, A[i]);
11             }
12         }
13         return res+1;
14     }
15 };