Insertion and sorting in a sequence of numbers minimizing the maximum sum of a contiguous subsequence ?
Let A  be a sequence of n?0 n ? 0 real numbers. A subsequence of A is a sequence of contiguous elements of A. A maximum scoring subsequence of A  is a subsequence with largest sum of its elements, which can be found in O(n) O ( n ) time by Kadane?s dynamic programming algorithm. We consider in this paper two problems involving maximal scoring subsequences of a sequence. Both of these problems arise in the context of sequencing tasks to minimize the maximum renewal cumulative cost. The first one, which is called INSERTION IN A SEQUENCE WITH SCORES (ISS), consists in inserting a given real number x in A  in such a way to minimize the sum of a maximum scoring subsequence of the resulting sequence, which can be easily done in O(n2) O ( n 2 ) time by successively applying Kadane?s algorithm to compute the maximum scoring subsequence of the resulting sequence corresponding to each possible insertion position for x . We show in this paper that the ISS problem can be solved in linear time and space with a more specialized algorithm. The second problem we consider in this paper is the SORTING A SEQUENCE BY SCORES (SSS) one, stated as follows: find a permutation A? A ? of A that minimizes the sum of a maximum scoring subsequence. We show that the SSS problem is strongly NP-Hard and give a 2-approximation algorithm for it.
maximum scoring subsequence maximum renewal cumulative cost insertion in a sequence maximum sum problem