import static org.assertj.core.api.Assertions.assertThat;

/**
 * Given an array which consists of non-negative integers and an integer m,
 * you can split the array into m non-empty continuous subarrays.
 * Write an algorithm to minimize the largest sum among these m subarrays.

 Note:
 If n is the length of array, assume the following constraints are satisfied:

 1 ≤ n ≤ 1000
 1 ≤ m ≤ min(50, n)
 Examples:

 Input:
 nums = [7,2,5,10,8]
 m = 2

 Output:
 18

 Explanation:
 There are four ways to split nums into two subarrays.
 The best way is to split it into [7,2,5] and [10,8],
 where the largest sum among the two subarrays is only 18.
 */

public class SplitArrayLargestSum {
    /**
     * 算法描述如下：
     *   给定任意一个数组，举例：
     *   【1， 2， 3】
     *     如果把这个数组分成三份，那么我们能得到的最小的数组和即是这个数组中的最大元素，这里是3
     *     如果把这个数组分成一份，那么我们能得到的最大的数组和就是这个数组中所有元素的和，这里是6
     *   所以对任意数组来说，我们要找的答案肯定在[最大元素，所有元素和]这个范围内
     *   那么具体如何缩小这个范围？
     *   1. 因为题目要求找出"连续数组和"，所以我们可以从某个数字开始（这里选择（max+min）/ 2)，看看如果我们每次都尽量多的取数字求和，
     *      使得尽可能多的数字小于这个中值，然后看看最后能分成多少组。
     *   2. 如果可以分成m组，那么说明我们的M值有可能是所求的答案，也有可能是当前的中值取得太小了，所以我们把 max = mid - 1 后继续
     *   3. 如果不能分成m组，那说明这个m太小了，不能是所求答案，所以我们要更新 min = mid + 1 然后再继续
     *   最后的min就是我们要求的答案
     *
     */
    public int splitArray(int[] nums, int m) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        int min = 0, max = 0;
        //找出可能出现的最大和最小值
        for(int num : nums) {
            min = Math.max(min, num);
            max += num;
        }
        if(m == 1) return max;
        //二分查找
        while(min <= max) {
            int mid = min + (max - min) / 2;
            if(canFit(mid, nums, m)) {
                //如果这些数字可以分成大小为mid的m组，说明有可能这个数字取的太大了，再减小
                max = mid - 1;
            } else {
                //如果不能分成大小为mid的m组，那么一定是这个mid数值取的太小了
                min = mid + 1;
            }
        }
        return min;
    }

    private boolean canFit(int size, int[] nums, int m) {
        int numGroups = 1;
        int sum = 0;
        for(int num : nums) {
            sum += num;
            //一直更新sum，直到比size大，此时sum自动成为当前的num，然后这个sum就是下一个分组的第一个数字
            if(sum > size) {
                sum = num;
                numGroups++;
                if(numGroups > m) {
                    return false;
                }
            }
        }
        return true;
    }

    public void test() {
        int[] nums1 = {7, 2, 5, 10, 8};
        assertThat(splitArray(nums1, 2)).isEqualTo(18);

        int[] nums2 = {1, 1, 1, 1, 1};
        assertThat(splitArray(nums2, 2)).isEqualTo(3);
    }

    public static void main(String[] args) {
        SplitArrayLargestSum o = new SplitArrayLargestSum();
        o.test();
    }
}