Abstract: Given a sequence X={x1,x2,…,xn} 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(knlogn) and space complexity O(n) was given.

Key words: Algorithm, Time complexity, Space complexity, Linear partition problem.

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

关键词: 算法, 时间复杂度, 空间复杂度, 线性划分问题