Efficient Algorithms for Some Variants of the Maximum-Sum Segment Problem

找尋最大總和區間是個既基礎且重要的數列分析問題。給定一個實數數列A，我們找區間A(i,j)使得該區間的總和為最大。這類問題在生物序列上有找重複區段、富含C,G的區域以及設計低時間複雜度的篩選器等應用。本篇碩士論文探討兩種最大總和區間的變型問題，並提出解決的快速演算法。

我們研究前k大總和區間問題並且提出時間複雜度為O(n+klogk)的演算法。當我們要求答案要按照總和由大到小排列，我們是第一個提出k < n情況下的最佳解。考慮前k大總和區間問題在d維以及每維長度為n的情形下，我們的演算法時間複雜度是O(n^{2d-1}+klogk)。此外，我們也提出最大總和區間符合平均值下限或上限的線性演算法。