[Swift]LeetCode410.分割数组的最大值|SplitArrayLargestSum

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：为敢（WeiGanTechnologies）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10330269.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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.

给定一个非负整数数组和一个整数 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，在所有情况中最小。

12ms

 1 class Solution {
 2     func splitArray(_ nums: [Int], _ m: Int) -> Int {
 3         var nums = nums
 4         var left:Int = 0
 5         var right:Int = 0
 6         for i in 0..<nums.count
 7         {
 8             left = max(left, nums[i])
 9             right += nums[i]
10         }
11         while (left < right)
12         {
13             var mid:Int = left + (right - left) / 2
14             if canSplit(&nums, m, mid)
15             {
16                 right = mid
17             }
18             else
19             {
20                 left = mid + 1
21             }
22         }
23         return left
24     }
25     
26     func canSplit(_ nums:inout [Int], _ m: Int, _ sum: Int) -> Bool
27     {
28         var cnt:Int = 1
29         var curSum:Int = 0
30         for i in 0..<nums.count
31         {
32             curSum += nums[i]
33             if curSum > sum
34             {
35                 curSum = nums[i]
36                 cnt += 1
37                 if cnt > m
38                 {
39                     return false
40                 }
41             }
42         }
43         return true
44     }
45 }