A Maximal Local Maximum-Sum Segment Data Structure

Yoshifumi SAKAI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.9   pp.1541-1542
Publication Date: 2018/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.1541
Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
algorithms,  sequence of real numbers,  maximum-sum segment,  

Full Text: PDF(226.1KB)
>>Buy this Article


Summary: 
A linear-time constructible data structure for a real number sequence supporting O(1)-time queries of the maximal local maximum-sum segment of any contiguous subsequence containing any specific position is proposed, where a local maximum-sum segment is a segment whose maximum-sum segment is itself.