Approximating the maximum consecutive subsums of a sequence

DOI10.1016/J.TCS.2013.05.032zbMATH Open1284.68483OpenAlexW2092717367MaRDI QIDQ2437755FDOQ2437755

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

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

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)

Cites Work

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

Cited In (7)

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

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)