一道字节算法面试题

文章预览

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. 暴力求解 暴力解法 是最简单的，但也是最复杂的。将一个长度为 的数组切成 个连续段，总共有 种切法。这是因为要完成一种切分，我们只需要在 个间隔中选 个间隔作为切割点： 暴力解法就是对 ………………………………