Codility: Lesson 12 Min Max Division

LeetCode 410 - Split Array Largest Sum
https://codility.com/programmers/lessons/12

You are given integers K, M and a non-empty zero-indexed array A consisting of N integers. Every element of the array is not greater than M.

You should divide this array into K blocks of consecutive elements. The size of the block is any integer between 0 and N. Every element of the array should belong to some block.

The sum of the block from X to Y equals A[X] + A[X + 1] + ... + A[Y]. The sum of empty block equals 0.

The large sum is the maximal sum of any block.

For example, you are given integers K = 3, M = 5 and array A such that:

  A[0] = 2
  A[1] = 1
  A[2] = 5
  A[3] = 1
  A[4] = 2
  A[5] = 2
  A[6] = 2

The array can be divided, for example, into the following blocks:

• [2, 1, 5, 1, 2, 2, 2], [], [] with a large sum of 15;
• [2], [1, 5, 1, 2], [2, 2] with a large sum of 9;
• [2, 1, 5], [], [1, 2, 2, 2] with a large sum of 8;
• [2, 1], [5, 1], [2, 2, 2] with a large sum of 6.

The goal is to minimize the large sum. In the above example, 6 is the minimal large sum.

Logically, it seems to be similar with the boron2013 (Flags) challenge by Codility.

http://blog.csdn.net/caopengcs/article/details/41834173

典型的二分我们可以。二分一个最大段的和，然后我们一段一段地加，超过要加的值，就开始一段新的。这个方法得力于都是非负整数……

简单说一下复杂度，二分问题的框架就是 二分 ＋ 判断。 判断部分显然是O(N)的。 二分的复杂度取决于二分的区间大小。我们的二分区间左端点可以认为是min(A[i])，也可以认为是0，反正区间大点也关系，右端点最大是N * M，那么二分的复杂度是O(log(N * M)) = O(logN + logM) = O(2 * log(max(M, N)) = O(log(max(M, N)) = O(log (M + N)) 所以算上检测的复杂度就达到要求的那个了。

https://github.com/acprimer/Codility/blob/master/src/Lesson12/MinMaxDivision.java
    public int solution(int K, int M, int[] A) {
        int n = A.length;
        int sum = 0, max = 0;
        for (int i = 0; i < n; i++) {
            sum += A[i];
            max = Math.max(max, A[i]);
        }
        int left = max, right = sum;
        while (left <= right) {
            int mid = (left + right) >> 1;
            int intervals = countIntervals(A, mid);
            if (intervals > K) {
                left = mid + 1;
            } else right = mid - 1;
        }
        return left;
    }

    private int countIntervals(int[] A, int target) {
        int sum = 0, count = 0;
        for (int i = 0; i < A.length; i++) {
            sum += A[i];
            if (sum > target) {
                count++;
                sum = A[i];
            }
        }
        return count + (sum > 0 ? 1 : 0);
    }
http://codesays.com/2014/solution-to-min-max-division-by-codility/

int TestLargeSum(const std::vector < int > &A, int K,int LargeSum)

{

    int i,n,j;

    n= A.size();

    long long sum;

    sum=0;

    j=0;

    for (i=0;i < n;i++)

    {

        sum += A[i];

        if (sum > LargeSum)

        {

            j++;

            if (j > (K-1)) return 0;

            sum =A[i];

        }

    }

    return 1;

}

int solution(int K, vector < int > &A)

{

    int i,n,Amax,LargeSum;

    int r,b,e,LargeSumR;

    n = A.size();

    LargeSum=0;

    for (i=K-1; i < n; i++) LargeSum += A[i];

    Amax=0;

    for (i=0;i < n;i++) if ( A[i] > Amax ) Amax=A[i];

    if (K==n) return Amax;

    LargeSum= max(Amax,LargeSum);

    b= Amax;

    e= LargeSum;

    if (e < b) swap(e,b);

    LargeSumR=e;

    // BinSearch

    while (b <= e)

    {

        LargeSum = (b+e)/2;

        r = TestLargeSum(A,K,LargeSum);

        if ( r )

        {

            e = LargeSum -1;

            LargeSumR= LargeSum;

        }

        else

        {

            b = LargeSum +1;

        }

    }

    return LargeSumR;

}

Python code: http://www.martinkysel.com/codility-minmaxdivision-solution/