  Sequence partition problems arise in many fields, such as sequential data
analysis, information transmission, and parallel computing. In this paper, we
study the following partition problem variant: given a sequence of $n$ items
$1,\ldots,n$, where each item $i$ is associated with weight $w_i$ and another
parameter $s_i$, partition the sequence into several consecutive subsequences,
so that the total weight of each subsequence is no more than a threshold $w_0$,
and the sum of the largest $s_i$ in each subsequence is minimized.
  This problem admits a straightforward solution based on dynamic programming,
which costs $O(n^2)$ time and can be improved to $O(n\log n)$ time easily. Our
contribution is an $O(n)$ time algorithm, which is nontrivial yet easy to
implement. We also study the corresponding tree partition problem. We prove
that the problem on the tree is NP-complete and we present an $O(w_0 n^2)$ time
($O(w_0^2n^2)$ time, respectively) algorithm for the unit weight (integer
weight, respectively) case.

Data Structures and Algorithms;Optimization and Control