对于给定的一个长度为 NN 的正整数数列 AA ,现要将其分成 MM 段,并要求每段连续,且每段和的最大值最小。
例如,将数列 4 \ \ 2 \ \ 4 \ \ 5 \ \ 14 2 4 5 1 要分成 33 段:
若分为 [4[4 2][42][4 5][1]5][1],各段的和分别为 6, 9, 16,9,1 ,和的最大值为 99;
若分为 [4][2[4][2 4][54][5 1]1],各段的和分别为 4, 6, 64,6,6 ,和的最大值为 66;
并且无论如何分段,最大值不会小于 66。
所以可以得到要将数列 4 \ \ 2 \ \ 4 \ \ 5 \ \ 14 2 4 5 1 要分成 33 段,每段和的最大值最小为 66 。