An algorithm for a generalized maximum subsequence problem

We consider a generalization of the maximum subsequence problem. Given an array a(1),..., a(2) of real numbers, the generalized problem consists in finding an interval [i, j] such that the length and the sum of the subsequence a(i),..., a(j) maximize a given quasiconvex function f. Problems of this type occur, e.g., in bioinformatics. We show that the generalized problem can be solved in time O(n log n). As an example, we show how the so-called multiresolution criteria problem can be solved in time O(n log n).