趙坤茂臺灣大學：資訊工程學研究所鄭智懷Cheng, Chih-HuaiChih-HuaiCheng2007-11-262018-07-052007-11-262018-07-052006http://ntur.lib.ntu.edu.tw//handle/246246/54107找尋最大總和區間是個既基礎且重要的數列分析問題。給定一個實數數列A，我們找區間A(i,j)使得該區間的總和為最大。這類問題在生物序列上有找重複區段、富含C,G的區域以及設計低時間複雜度的篩選器等應用。本篇碩士論文探討兩種最大總和區間的變型問題，並提出解決的快速演算法。 我們研究前k大總和區間問題並且提出時間複雜度為O(n+klogk)的演算法。當我們要求答案要按照總和由大到小排列，我們是第一個提出k < n情況下的最佳解。考慮前k大總和區間問題在d維以及每維長度為n的情形下，我們的演算法時間複雜度是O(n^{2d-1}+klogk)。此外，我們也提出最大總和區間符合平均值下限或上限的線性演算法。Contents Title ii Tabel of Contents ii Acknowledgements iii Abstract in Chinese iv Abstract v 1 Introduction 1 2 The k Maximum-Sum Segment Problem 3 2.1 An Iterative Partial-Table Building Approach . . . . . . . . . . . . . . . 4 2.2 Improving on the Time Complexity in the k < n Case . . . . . . . . . . . 9 2.3 The Problem of k Maximum-Sum Segments in Order . . . . . . . . . . . 10 2.4 The k Maximum-Sum Subarray Problem . . . . . . . . . . . . . . . . . . 12 3 The Problem of the Maximum-Sum Segment Satisfying an Average Constraint 15 3.1 A Linear-time Algorithm for Finding the Maximum-Sum Segment Satisfying an Average Lower Bound . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 A Linear-time Algorithm for Finding the Maximum-Sum Segment Satisfying an Average Upper Bound . . . . . . . . . . . . . . . . . . . . . . . 21 4 Future Works 24 4.1 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24en-US最大總和區間maximum-sum segmentthesis