Split Array Largest Sum 二分查找应用 C实现

• 题目描述
  

• 初步分析
  该题乍一看没有什么思路，于是我便直接思考用二分查找怎么做（因为该题是在二分查找分类下的）。

  那对什么东西来应用二分查找呢？
  1、是对在m个子串的条件下，来找寻（m-1）个cut的位置上应用二分查找吗？如果是那样的话，二分查找的起始边界是什么，跳出查找的循环条件又是什么？显然这两个问题是很难具体确认的，我们应该再想想其他的。
  2、本题最终需返回的是最小子串划分方法的最大子串值（我把它叫做minmax），那要不我们直接对这个值应用二分查找？那二分查找的起始边界是什么，跳出查找的循环条件又是什么呢？欸，这个思路似乎可行，我们具体来看（见下文）。

• 具体分析

  通过来回答以下的问题，来更清晰的认识代码该怎么写。

  1、minmax的可能的最大最小值是多少？
    最小值（low或left的初值）：nums数组中的最大元素值。
    最大值（high或right的初值）：nums数组中所有元素的和。
    举例，nums=[2,3,7,5,9],则minmax的最小值为9，最大值为26

  2、如何缩小范围？也即low、high改变取值的条件（low=mid+1，high=mid-1）是什么？
    这里是算法的核心部分。
    若用一句话总结，便是看在进行子串和不大于mid的分割后，看分割的次数和m-1的关系。
    什么叫进行子串和不大于mid的分割？
    我们举个例子，nums=[2,3,7,5,9],第一轮mid=（low+high）/2=17。我们从左边的第一个数开始累加，subSum=2+3+7+5=17，当再加上9时，sumSum=17+9=26，已经大于mid，所以在5和9之间应该割一刀，9作为第二个子串的第一个元素。在本轮中，分割次数=1.
    如何判断分割次数和m-1的关系呢？
    如果分割次数>m-1,说明我们按mid来尽可能地让每个子串足够长，也不能在m-1的次数（包括m-1）内结束分割，mid的值取得太小了，所以应该low=mid+1，进行下一轮的判断。
    如果分割次数 <=m-1,说明我们可以在m-1的次数（包括m-1）内结束分割，mid的值取得合理。但该mid的值一定就是最小情况下的最大值吗？不一定！（举个例子，nums=[2,3,7,5,9]，假设m=2，当mid=17时，分割次数==m-1=1，但我们知道最终的答案可以更小，为14）所以，我们就试试去更小的值看看，即high=mid-1，进入下一轮的判断。

  3、结束循环的条件是什么？
    根据问题2中所述，若mid取得太小而导 致进行了大于m-1次的分割，我们会low=mid+1来向上缩小范围；若mid取得值可以进行了小于等于m-1次分割了，为了找到可能存在的更小mid，我们会令high=mid-1向小缩小范围。
    所以，该二分查找结束循环的条件是low=high，无中途break跳出的情况。

  4、可能存在的疑惑
    你可能会问，“为什么分割次数小于m-1而非等于，你依然会觉得mid的值是合理的呢？”
    因为该分割次数是从左往右，让每个子串尽可能的长而得来的。而事实上，我们求取的结果并不需要让每个子串尽可能长才可以。若分割次数小于m-1，那我们随便补上几刀就能使分割次数=m-1了。如nums=[2,3,1,1,1,1,1]，mid=3，m=5,按照算法分割出的子串是[2]，[3],[1,1,1],[1,1],那我可以在[1,1,1]上补一刀，变成[1,1]和[1]，不就也m-1次分割了吗。
    这个合理的mid的值也不一定是最终结果，因为有可能还有比它小且合理的结果存在，所以我们要high=mid-1再看看。所以这个问题是和向下搜索更小的以及向下的底线（low）相辅相成的。

• 代码

int judge(int* nums, int numsSize, int m,long mid){
    int i,count;   //count为分割的次数，等于子串数-1
    long subSum;

    subSum=0;
    count=0;
    for(i=0;i<numsSize;i++){
        subSum+=nums[i];
        if(subSum==mid){
            //从下一个元素开始下一个子串的构建
            subSum=0;
            if(i!=numsSize-1)
                count++;
        }
        else if(subSum>mid){
            //从本元素开始下一个子串的构建
            count++;
            subSum=nums[i];
        }
    }
    if(count>m-1)
        return true;
    else
        return false;

}
int splitArray(int* nums, int numsSize, int m) {
    int l,max;
    long r,sum,mid;
    int i;

    //获得l、r的初值
    max=nums[0];
    sum=0;
    for(i=0;i<numsSize;i++){
        if(nums[i]>max)
            max=nums[i];
        sum+=nums[i];
    }   
    l=max;
    r=sum;

    while(l<=r){   //所有可能值已搜索完，l是最小的且满足条件的值
        mid=(l+r)/2;
        if(judge(nums,numsSize,m,mid))
            l=mid+1;    //mid取的太小，向上缩小范围
        else
            r=mid-1;    //mid的值可能是结果，但有可能还有比它小且满足条件的值，所以向下缩小范围
    }

    return l;
}

• 运行时间
  如下图所示，
  

• 后话
  该题我一开始在写二分查找的时候，把分割次数等于m-1和分割次数小于m-1的情况拆开来写，认为只有分割次数等于m-1的才可能是答案，当意识到不一定要让每个子串都取足够长也可能是答案时，代码被改得混乱不堪，最终决定重写，才得到上面的代码。得到一个启发，分析问题要多留心可能的情况，把该合并的情况合并了，代码也就会写得比较容易了。