Thinking process

How to extract the model?

• how to cut the array into (k - 1) subarray to get the smallest largest subarray sum?
• e.g. 3 9 2 4 k=3 => 3 | 9 | 2 4 and the result is 9

But it's not time efficient to enumerate all possible subarrays

• the possible subarray sum is in the range [9, 18]
• find the smallest sum that can be obtained by cutting into k pieces
  • that is to say, find the first position at which the result is k after passing the value into a checking function

But considering the following example

• [1, 2] k = 5
• So, it's possible that you can't cut into exact k pieces. So, the condition changes to find the smallest subarray sum that can be obtained by cutting the array into k or smaller than k pieces.
• if true, move right pointer to the middle, in order to find whether smaller one exist
• else, move left pointer right

Time complexity

public class Solution {
    /**
     * @param pages: an array of integers
     * @param k: an integer
     * @return: an integer
     */
    public int copyBooks(int[] pages, int k) {
        // write your code here
        if (pages == null || pages.length == 0) return 0;

        int start = pages[0];
        int end = pages[0];
        for (int i = 1; i < pages.length; ++i) {
            start = Math.max(start, pages[i]);
            end += pages[i];
        }

        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;

            if (getMinSum(mid, pages) <= k) {
                end = mid;
            } else {
                start = mid;
            }
        }

        if (getMinSum(start, pages) <= k) return start;
        if (getMinSum(end, pages) == k) return end;

        return 0;
    }

    private int getMinSum(int max, int[] pages) {
        int result = 1;
        int curr = 0;
        for (int i = 0; i < pages.length; ++i) {
            if (curr + pages[i] > max) {
                result++;
                curr = 0;
            }
            curr += pages[i];
        }

        return result;
    }
}

To do dynamic programming solution

backpack

http://www.jiuzhang.com/solutions/copy-books/