Linear time computation of the maximal linear and circular sums of multiple independent insertions into a sequence

DOI10.1016/J.TCS.2016.11.005zbMATH Open1356.68300arXiv1307.1447OpenAlexW2262952408MaRDI QIDQ501652FDOQ501652

Ricardo C. Corrêa, Pablo M. S. Farias

Publication date: 9 January 2017

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

Abstract: The maximal sum of a sequence "A" of "n" real numbers is the greatest sum of all elements of any strictly contiguous and possibly empty subsequence of "A", and it can be computed in "O(n)" time by means of Kadane's algorithm. Letting "A^(x -> p)" denote the sequence which results from inserting a real number "x" between elements "A[p-1]" and "A[p]", we show how the maximal sum of "A^(x -> p)" can be computed in "O(1)" worst-case time for any given "x" and "p", provided that an "O(n)" time preprocessing step has already been executed on "A". In particular, this implies that, given "m" pairs "(x_0, p_0), ..., (x_{m-1}, p_{m-1})", we can compute the maximal sums of sequences "A^(x_0 -> p_0), ..., A^(x_{m-1} -> p_{m-1})" in "O(n+m)" time, which matches the lower bound imposed by the problem input size, and also improves on the straightforward strategy of applying Kadane's algorithm to each sequence "A^(x_i -> p_i)", which takes a total of "Theta(n.m)" time. Our main contribution, however, is to obtain the same time bound for the more complicated problem of computing the greatest sum of all elements of any strictly or circularly contiguous and possibly empty subsequence of "A^(x -> p)". Our algorithms are easy to implement in practice, and they were motivated by and find application in a buffer minimization problem on wireless mesh networks.

Full work available at URL: https://arxiv.org/abs/1307.1447

Recommendations

• A Linear Time Algorithm for the k Maximal Sums Problem
• Algorithms and Computation
• Ranking \(k\) maximum sums
• Efficient algorithms for \(k\) maximum sums
• Insertion and sorting in a sequence of numbers minimizing the maximum sum of a contiguous subsequence

zbMATH Keywords

priority queuecircular subsequenceFIFO ordermaximal sum subsequencemultiple insertions into a sequence

Mathematics Subject Classification ID

Algorithms on strings (68W32) Network protocols (68M12)

Cites Work

• Data Mining with optimized two-dimensional association rules
• Wireless mesh networks: a survey
• Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
• A note on a standard strategy for developing loop invariants and loops
• Sequencing to minimize the maximum renewal cumulative cost
• A Linear Time Algorithm for the k Maximal Sums Problem
• A Parallel Algorithm for Finding All Successive Minimal Maximum Subsequences
• Selecting Sums in Arrays
• Insertion and sorting in a sequence of numbers minimizing the maximum sum of a contiguous subsequence
• On the complexity of bandwidth allocation in radio networks
• On the range maximum-sum segment query problem
• Optimal algorithms for the average-constrained maximum-sum segment problem

Cited In (2)

• Insertion and sorting in a sequence of numbers minimizing the maximum sum of a contiguous subsequence
• Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence

This page was built for publication: Linear time computation of the maximal linear and circular sums of multiple independent insertions into a sequence

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