文章基本信息

标题：Algorithms for the Maximum Subarray Problem Based on Matrix Multiplication
本地全文：下载
作者：Hisao TAMAKI ; Takeshi TOKUYAMA
期刊名称：Interdisciplinary Information Sciences
印刷版ISSN：1340-9050
电子版ISSN：1347-6157
出版年度：2000
卷号：6
期号：2
页码：99-104
DOI：10.4036/iis.2000.99
出版社：The Editorial Committee of the Interdisciplinary Information Sciences
摘要：Given an M × N array of reals, we want to find a rectangular contiguous subarray such that the sum of the entries in the subarray is maximized. Since Bentley posed this problem in his Programming Pearls column in 1984 with an O ( NM ²) time solution, no progress on the sequential complexity has been reported to date. We give the first subcubic algorithm, by reducing the problem to “funny matrix multiplication”, where the scalar product and addition in usual matrix multiplication are replaced by addition and max operations, respectively. We also give a faster ε-approximation algorithm via the same reduction.
关键词：Theoretical Computer Science;Algorithms;Complexity;Maximum Subarray;Matrix Multiplication