HZC 早闻 LWH 对数学研究颇深,于是带着以下问题去考他:对于给定的一个长度为N的正整数数列 ,现要将其分成 段,并要求每段连续,且每段和的最大值最小。
例如,将数列 要分成 段:
若分为 ,各段的和分别为 ,和的最大值为 ;
若分为 ,各段的和分别为 ,和的最大值为 。
并且无论如何分段,最大值不会小于 ,所以可以得到要将数列 要分成 段,每段和的最大值最小为 。
然而,LWH 只是外强中干,他开始虚了,现在请你帮他编程解决这个问题。
输入
第 行包含两个正整数 。
第 行包含 个空格隔开的非负整数 ,表示数列各项的值。
输入保证 。
输出
输出仅包含一个正整数,表示每段和最小的最大值。
样例
标准输入 复制文本 |
5 3 4 2 4 5 1 |
标准输出 复制文本 |
6 |
来源
2019 软件学院蓝桥杯热身赛 (For 17/18/19)