LeetCode 410. Split Array Largest Sum
题目描述:
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: Given m satisfies the following constraint: 1 ≤ m ≤ length(nums) ≤ 14,000.
Examples:
1
2
3
4
5
6
7
8
9
10
11 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.
这道题我是采用二分搜索的方法解的. 虽然要想到对整个int型范围进行二分搜索还是不太容易, 但是只要想到这一点, 问题就基本解决了, 剩下的就可以通过贪心来判断数组能不能被分成m个并且保证最大的和不超过一个给定的值. 二分搜索上界是INT_MAX, 而下界是数组中的最大值.
1 | class Solution { |