小米2018-09-20在线笔试最优解

题目描述

依次提供n个正整数A1，A2，…，An，将这n个数值划分为m个区间，每个区间内所有数值之和定义为该区间的权重，而所有m个区间中权重的最大值即为此次划分的总权重。问题要求在所有可能的划分方式中，找到总权重的最小值是多少？

输入

第一行依次给出正整数n与m，以单个空格分隔；（n<=10000，m<=10000，m<=n）

第二行依次给出n个正整数，以单个空格分隔A1，A2，…，An（Ai<=10000）

输出

总权重的最小值

样例输入

5 3

1 4 2 3 5

样例输出

5

Hint

当划分为14 | 2 3 | 5时，三段的权重分别为5、5、5，此时总权重达到最小值。

题目解析

本题目源自LeetCode的 [410. Split Array Largest Sum