#!/usr/bin/env python
# coding:utf-8

"""
410. 分割数组的最大值
难度
困难

给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

注意:
数组长度 n 满足以下条件:

1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)
示例:

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

输出:
18

解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
"""


# ================================================================================
"""
方法:
    二分查找
思路:
    结果的范围在: max(nums) 和 sum(nums) 之间，利用二分查找逐步缩小区间范围，当区间长度为1时，问题得解。
步骤:
    每次计算一个 mid 值，代表当前猜测的答案，
    然后模拟划分子数组的过程，得到用这个 mid 值划分的子区间数 count，比较 count 和 m 的关系来更新区间范围。
"""
"""
时间复杂度：
    O( len(nums)*log(sum(nums)) )
空间复杂度:
    O(1)
"""
class Solution(object):
    def splitArray(self, nums, m):
        """
        :type nums: List[int]
        :type m: int
        :rtype: int
        """
        # 处理特殊情况
        if len(nums) == m:
            return max(nums)
        # len(nums) > m
        low, high = max(nums), sum(nums)
        while low < high:
            mid = (low + high)/2
            # ==================== 模拟划分子数组的过程，求得划分出来的分组数（后面用来跟已知的分组数做比较）
            # 当前分组的和
            current = 0
            # 分组计数
            count = 1
            for n in nums:
                # 把 nums 中的元素逐个累加到 current 中，直到当前分组的和超出了最大值 mid
                current += n
                if current > mid:
                    # 当前分组的和超出了最大值 mid，则需要把当前元素放在下一个分组
                    current = n
                    count += 1
                    pass
                pass
            # ==================== 模拟划分子数组的过程，求得划分出来的分组数（后面用来跟已知的分组数做比较）
            if count > m:
                # 分出了比要求多的子数组，多切了几刀，说明 mid 应该加大，这样能使子数组的个数减少
                low = mid + 1
            else:
                # count <= m
                # 分出了比要求少的子数组，少切了几刀，说明 mid 应该减小，这样能使子数组的个数增加
                high = mid
            pass
        return low

# ================================================================================
# ================================================================================
# ================================================================================

