915. 分割数组-动态规划算法

915. 分割数组-动态规划算法

给定一个数组 nums ，将其划分为两个连续子数组 left 和 right， 使得：

left 中的每个元素都小于或等于 right 中的每个元素。
left 和 right 都是非空的。
left 的长度要尽可能小。

在完成这样的分组后返回 left 的 长度 。

用例可以保证存在这样的划分方法。

示例 1：

输入：nums = [5,0,3,8,6]
输出：3
解释：left = [5,0,3]，right = [8,6]

示例 2：

输入：nums = [1,1,1,0,6,12]
输出：4
解释：left = [1,1,1,0]，right = [6,12]

int partitionDisjoint(int* nums, int numsSize){
    int rmax[numsSize];
    int rmin[numsSize];
    int max=nums[0];
    rmax[0]=max;
    for(int i=1;i<numsSize;i++){
        if(max<nums[i]){
            max=nums[i];
        }
        rmax[i]=max;
    }
    rmin[numsSize-1]=nums[numsSize-1];
    int min=nums[numsSize-1];

     for(int i=numsSize-2;i>=0;i--){
        if(min>nums[i]){
            min=nums[i];
        }
        rmin[i]=min;
    }
    for(int i=0;i<numsSize-1;i++){
        if(rmax[i]<=rmin[i+1]){
            return i+1;
        }
    }
    return numsSize;

}