leetcode 410. 分割数组的最大值

Posted on | In ,

题目

Split Array Largest Sum

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

题解

动态规划

通过看答案看到了这样的动态规划转移公式：

$f[i][j]$ 表示在前i个节点分为j个子数组时的最小值；要得到他就得是遍历 $0-i$ 中的所有情况；然而在 $ k < j-1 $ 的情况下也就是k个节点不够 $j-1$ 个子数组分。这种情况下的值属于不可能的情况，一般给他一个很大的值。它给$min$提供了一个不可能的选项，所以不会选到它。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def splitArray(self, nums, m):
        n = len(nums)
        f = [[10**18] * (m + 1) for _ in range(n+1)]
        sub = [0]
        for elem in nums:
            sub.append(sub[-1] + elem)
        f[0][0] = 0
        for i in range(1,n+1):
            for j in range(1, min(i, m) + 1):
                for k in range(i):
                    f[i][j] = min(f[i][j], max(f[k][j-1], sub[i] - sub[k]))
        return f[n][m]

二分查找

这里想要找到一个值x，这个值是分成的cnt个子数组和的最大值，所以每一个子数组都不大于他。

我们先不管能分成几个子数组。就先用数组中的最大值x来卡，来把数组分开

如果连续数组不大于x， 如果$n$个连续元素的和不大于x，那么他们就可以分到一个子数组中，如果再往后，$n+1$个元素之和大于x。那么从第$n+1$个元素分开，另放入一个子数组。由于最大值x在数组中前后加起来都一定大于x，所以他单独一个在一个子数组里。如果此时分成的子数组的数量大于所想要的m个子数组。那么我们就需要提高x的值，来使得子数组数量减少到刚好m。或者x值太高了，使得子数组的数量太少了。我们就需要减少x的值，使得子数组增多到m。之前这是贪心算法的思想。而后面调节x则可以用二分查找的方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        def check(x: int) -> bool:
            total, cnt = 0, 1
            for num in nums:
                if total + num > x:
                    cnt += 1
                    total = num
                else:
                    total += num
            return cnt <= m


        left = max(nums)
        right = sum(nums)
        while left < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1

        return left