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段

现在我们来细致地分析下这两个约束条件。其他连续段段内数字之和都比