Split Array Largest Sum

2017年8月28日20:22:09 发表评论 33

410. 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

  • 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.

solve:

二分法边界:

[st, ed]  离散域上

分割: [st, mid-1] mid [mid+1, ed]

运行条件:st <= ed

[st, ed)  实数域上

分割:[st, mid) mid [mid+1, ed)

运行条件:st < ed

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: