1. 题目描述

今天，我们来看字节跳动的一道基础算法面试题，也是牛客网中比较基础的题目[1]，需要现场编程解答，编程语言不限。

题目描述如下：

描述：给定一个n个数字的序列a={a1,a2,…,an}，现在想把这个序列分成k个连续段，分出来的k个连续段的段内数字和的最小值最大是多少？

备注：

要求：时间复杂度小于

相关示例如下：

输入：n=4，k=2，a=[1,2,1,5]

返回值：4

说明：这个序列有3种分法

[1],[2,1,5]，数字和分别为1，8，最小值为1

[1,2][1,5]，数字和分别为3，6，最小值为3

[1,2,1],[5]数字和分别为4，5，最小值为4

所以最小值的最大值为4。

2. 暴力求解

暴力解法是最简单的，但也是最复杂的。将一个长度为 的数组切成 个连续段，总共有 种切法。这是因为要完成一种切分，我们只需要在 个间隔中选 个间隔作为切割点：

暴力解法就是对 种切法中的每一种切分，一一计算连续段内数字之和的最小值，然后再拿出来逐个比较，最终获得这个最小值的最大值。

暴力解法其实就是穷举法，它的复杂度实在是太高了，也不太好写。接下来，我们一起来看看简单的解法。

3. 问题分析

3.1 初步思考

要想有简单的解法，我们必须转换自己的思路。首先，我们来问自己两个问题：

• 这道题的变量有哪些？
• 数组大小 ，数组 ，连续段个数
• 哪些变量是可以遍历的？

第一个问题容易回答，第二个问题就不是那么简单了。

回想下，之前我们想要用暴力解法的时候，想要遍历的其实是 种切法。那么除此以外，还有没有同样非显式的可遍历的变量呢？

3.2 思路转换

一下想不出没关系的，我们再来问自己几个问题：

• 连续段段内数字之和最小是多少？
• 数组 的最小值
• 连续段段内数字之和最大是多少？
• 不超过数组 的数字之和

其实，我们已经问出了一个新的遍历条件，那就是这道题答案的可能范围。

也就是说我们知道了答案的可能值最小为数组元素的最小值，最大为数组元素之和，最终的答案就在由数组元素最小值与数组元素之和框定的范围之中。

到这里，我们的思路就可以转换了：从正面罗列所有可能的切分然后逐一比较，到罗列所有可能的答案再逐一排除。

3.3 约束条件

我们先假设这道题的答案是，然后再来问自己一个问题，这个问题也就是真正的答案需要满足的条件：

• 意味着什么？
• 是它对应的那种切法下所获得的连续段的段内数字之和的最小值。

这个答案好像是显而易见的，我们再问深一点，挖掘挖掘潜在的约束条件：

• 连续段段内数字之和最小意味着什么？
• 首先，其他的连续段段内数字之和都比它大。
• 其次，以 为标准进行切分需要满足至少分成K段

现在我们来细致地分析下这两个约束条件。其他连续段段内数字之和都比 大，意味着 。转换下不等式，就有 。也就是说若按照和大于等于 作为切割条件，最终获得连续段个数至少为 。

综上分析，我们得到了一个可行的解决方法：依次尝试 范围内的每一个值，并以相应值为切割条件尝试对数组 进行切分，如果不能切成至少 段，那么就再继续遍历。

4. 编程实现

下面是python3实现的代码：

#coding=utf-8
import sys

class Solution:
    def solve(self , n , k , a ):
        # write code here
        margin_min = min(a)
        margin_max = sum(a)
        # margin_max = int(sum(a)/k)
        for p_v in range(margin_max,margin_min-1,-1):
            tmp_sum = 0
            segment_count = 0
            for item in a:
                tmp_sum+=item
                if tmp_sum>=p_v:
                    segment_count+=1
                    tmp_sum=0
                    
            if segment_count>=k:
                return p_v

还需补充的是其实这道题的答案范围可进一步缩小为 ，这是因为由可得出。

下面是本地验证代码：

# 运行后结果为4
solution = Solution()
result = solution.solve(4,2,[1,2,1,5])
print(result)

其实今天我们并没有给出最优解法，提示一下最优解法可以考虑引入二分思想。不过还是来看一下，在牛客网上提交后的测试结果：

总结

今天我们一起学习了一道算法面试题。这道题本身不难，这其中的思路转换是最重要的，一旦我们充分思考和理解了思路转换过程中的各个问题，代码实现就不是难事儿了。

参考资料

[1] 题目: http://www.nowcoder.com/practice/829419bde0e946b6b4fe813ed3972db8