Approximating the maximum consecutive subsums of a sequence

DOI10.1016/J.TCS.2013.05.032MaRDI QIDQ2437755zbMATH OpenOpenAlexFDO

Authors Ferdinando Cicalese, Eduardo S. Laber, Oren Weimann, Raphael Yuster

Publication date 13 March 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2013.05.032

zbMATH Keywords

approximate pattern matchingpermutation pattern matchingParikh vectorsmaximum subsequence sum

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics on words (68R15) Algorithms on strings (68W32)

Recommendations

• Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence
• An extremal problem in subsequence sum
• scientific article; zbMATH DE number 4095614
• An approximation scheme for the problem of finding a subsequence
• On the number of subsequences with given sum
• On consecutive subset sums
• scientific article; zbMATH DE number 1555947
• Efficient Computation of the Maximum of the Sum of Two Sequences and Applications
• The Largest Sum-Free Subsequence from a Sequence of n Numbers
• An extremal problem for subset-sum-distinct sequences with congruence conditions

Cites work

• A fast string searching algorithm
• Algorithmic complexity of protein identification: Combinatorics of weighted strings
• Computational Science – ICCS 2005
• Efficient text fingerprinting via Parikh mapping
• Fast Pattern Matching in Strings
• Fast algorithms for finding disjoint subsequences with extremal densities
• Necklaces, Convolutions, and X + Y
• On approximate jumbled pattern matching in strings
• Scaled and permuted string matching
• Sub-quadratic time and linear space data structures for permutation matching in binary strings

Cited in

(7)

• Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence
• Insertion and sorting in a sequence of numbers minimizing the maximum sum of a contiguous subsequence
• An extremal problem in subsequence sum
• Bubble-flip -- a new generation algorithm for prefix normal words
• Finding the maximum subsequence sum on interconnection networks
• The Largest Sum-Free Subsequence from a Sequence of n Numbers
• Generating a Gray code for prefix normal words in amortized polylogarithmic time per word

This page was built for publication: Approximating the maximum consecutive subsums of a sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437755)