线性划分问题的一个改进算法

An Improved Algorithm for the Linear Partition Problem

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

Given a sequence X= { x1 ,x2, … ,xn } with n non-negative numbers and a positive integer k≤n, the linear partition problem requires to partition X into k or less than k subsequences, so as to minimize the maximum sum of elements over all subsequences. The known best algorithm for this problem is a dynamic programming algorithm with time complexity O（kn^2 ） and space complexity O（kn）. By using the properties of the non- negative sequence, an improved algorithm with time complexity O（knlogn） and space complexity O（n） was given.