论文部分内容阅读
给定一个由n个非负数构成的序列X={x1，x2，…，xn}及正整数k≤n，线性划分问题要求将该序列划分为不大于k段子序列，使得最小化各段子序列元素之和为最大值。目前已知该问题的最好算法是时间复杂度为O（kn^2）和空间复杂度为O（kn）的动态规划算法。利用非负数序列的性质，给出一个快速改进算法，其时间复杂度为O（knlogn），空间复杂度为O（n）。