pith. sign in

arxiv: 2604.23168 · v1 · submitted 2026-04-25 · 💻 cs.DS

Approximate Maintenance of Maximum Subarray Sum in the Sliding Window Model

Ryo Suzuki , Yutaro Yamaguchi This is my paper

Pith reviewed 2026-05-08 07:38 UTC · model grok-4.3

classification 💻 cs.DS
keywords sliding window modelmaximum subarray sumapproximation algorithmsdata streamssmooth histogramsublinear space
0
0 comments X

The pith

Refining the Smooth Histogram framework maintains a (1 ± ε) approximation to the maximum subarray sum over the most recent n stream elements using O(ε^{-1} (log n)^2) bits of space.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how to keep track of the largest sum of any contiguous segment within the latest n items of a data stream, without storing the entire window. Exact solutions need linear space, but the authors adapt the Smooth Histogram approach first to a constant-factor approximation with O((log n)^2) bits, then refine it to achieve any desired relative error ε while multiplying space by a 1/ε factor. The resulting per-update cost stays O(ε^{-1} log n) operations. A reader cares because many monitoring tasks on continuous data only need recent history, and sublinear space makes it feasible to run on long streams. If the refinement works as claimed, the space bound is asymptotically optimal for this problem.

Core claim

By first applying the Smooth Histogram framework to obtain a constant-factor approximation of the maximum subarray sum in O((log n)^2) bits and then refining the framework to preserve a (1 ± ε) guarantee, the algorithm maintains the desired approximation using O(ε^{-1} (log n)^2) bits of space and O(ε^{-1} log n) operations per update; the space complexity is asymptotically optimal.

What carries the argument

The refined Smooth Histogram framework, which maintains a collection of overlapping instances of the statistic over windows whose sizes decrease exponentially so that expirations can be handled without invalidating the maintained value.

If this is right

  • A constant-factor approximation is already possible with O((log n)^2) bits via the basic Smooth Histogram.
  • The (1 ± ε) version multiplies space by only a 1/ε factor while keeping update time linear in 1/ε times log n.
  • The space bound matches the lower bound for the problem up to constants.
  • The same maintenance cost applies uniformly across all windows of size n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same refinement technique may extend to other statistics that admit smooth histograms, such as minimum subarray sum or certain range aggregates.
  • In practice the method could be combined with sampling to handle very high update rates when ε is not tiny.
  • The logarithmic dependence on n suggests the approach remains viable even when windows grow to sizes that defeat linear-space methods.

Load-bearing premise

The Smooth Histogram admits a refinement that keeps the (1 ± ε) guarantee intact when old elements expire from the window.

What would settle it

A stream of length poly(n) on which any data structure using o(ε^{-1} (log n)^2) bits produces an estimate whose relative error exceeds ε on at least one window.

read the original abstract

In the sliding window model, we are required to maintain the target statistics over the most recent $n$ elements of a data stream, which is captured by a window of size $n$ sliding over the data stream. Exact computation usually requires space linear in $n$, and the central goal is approximate maintenance using sublinear space. In this paper, we study the problem of maintaining the maximum subarray sum in the sliding window model. While the classical Kadane's algorithm computes the exact answer using constant space in the static setting, it does not extend directly, because a new element makes the oldest one expire, which may invalidate the optimal subarray so far. Our first observation is that the so-called Smooth Histogram framework can lead to a constant-factor approximation (in the sense of relative error) using $O((\log n)^2)$ bits of space. We then refine this framework accordingly, which enables for any $\epsilon > 0$ to maintain a $(1 \pm \epsilon)$-approximation using $O(\epsilon^{-1}(\log n)^2)$ bits of space and $O(\epsilon^{-1}\log n)$ operations per update. The space complexity is asymptotically optimal.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper studies approximate maintenance of the maximum subarray sum over a sliding window of size n in a data stream. It first applies the Smooth Histogram framework to obtain a constant-factor approximation in O((log n)^2) bits of space. It then refines the framework to achieve a (1 ± ε)-approximation for any ε > 0, using O(ε^{-1}(log n)^2) bits of space and O(ε^{-1} log n) operations per update, and claims this space bound is asymptotically optimal.

Significance. If the refinement step is correct, the result gives a clean sublinear-space solution to a natural streaming problem where exact maintenance requires linear space. The approach builds directly on an existing framework with a targeted refinement, and the claimed asymptotic optimality (if supported by a matching lower bound) would be a strong point.

major comments (1)
  1. [Abstract] The abstract states that the space complexity O(ε^{-1}(log n)^2) is asymptotically optimal, but the provided text does not explicitly derive or cite a matching lower bound. Please add a reference or short argument establishing the lower bound (e.g., in the section presenting the upper bound).
minor comments (2)
  1. In the description of the constant-factor result, clarify how the Smooth Histogram buckets are maintained under element expiration without invalidating the constant-factor guarantee.
  2. The update-time bound O(ε^{-1} log n) is stated without an explicit breakdown; a short paragraph or table showing the per-bucket cost would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the constructive feedback. We are glad that the overall approach is viewed positively and that the result is considered significant provided the refinement is correct. We address the major comment point by point below.

read point-by-point responses

  1. Referee: [Abstract] The abstract states that the space complexity O(ε^{-1}(log n)^2) is asymptotically optimal, but the provided text does not explicitly derive or cite a matching lower bound. Please add a reference or short argument establishing the lower bound (e.g., in the section presenting the upper bound).

    Authors: We agree that the claim of asymptotic optimality in the abstract would be strengthened by an explicit lower bound argument or citation, which is currently not present in the manuscript. In the revised version, we will add a concise paragraph (approximately 1/3 page) in the section describing the (1±ε)-approximation algorithm. This paragraph will sketch a matching Ω(ε^{-1}(log n)^2) lower bound via a reduction from the communication complexity of the sliding-window maximum problem (which itself requires Ω(log n) space even for constant-factor approximation) combined with a standard ε-net argument to force the 1/ε factor; we will also cite the relevant streaming lower-bound literature on sliding windows. The abstract will remain unchanged as the added argument directly supports the existing claim. This is a minor revision. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected in derivation chain

full rationale

The paper applies the established Smooth Histogram framework (external prior work) to obtain a constant-factor approximation for maximum subarray sum under sliding windows using O((log n)^2) space, then refines the framework to achieve a (1±ε) approximation while preserving O(ε^{-1}(log n)^2) space and O(ε^{-1} log n) update time. No equation reduces the output approximation ratio or space bound directly to a fitted parameter, self-defined quantity, or prior result by the same authors. The refinement is presented as an independent technical step whose correctness is claimed to hold independently of the target quantity, with asymptotic optimality argued separately. No self-citation load-bearing, ansatz smuggling, or renaming of known results occurs in the load-bearing steps.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the applicability of the Smooth Histogram framework (assumed from prior work) and standard assumptions of the sliding-window streaming model; no new free parameters or invented entities are introduced.

axioms (2)
  • domain assumption The data arrives as an unbounded stream and the window of size n slides by expiring the oldest element on each update.
    Invoked in the problem definition and in the description of why Kadane's algorithm fails.
  • domain assumption The Smooth Histogram framework from prior literature can be applied to maintain approximate maximum subarray sums.
    Stated as the first observation and the basis for both the constant-factor and the (1±ε) results.

pith-pipeline@v0.9.0 · 5508 in / 1384 out tokens · 68583 ms · 2026-05-08T07:38:25.958942+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

  1. [1]

    Programming pearls: Algorithm design techniques.Communications of the ACM, 27(9):865–873, 1984

    Jon Bentley. Programming pearls: Algorithm design techniques.Communications of the ACM, 27(9):865–873, 1984

    work page 1984

  2. [2]

    Sliding window algorithms

    Vladimir Braverman. Sliding window algorithms. InEncyclopedia of Algorithms, Second Edition, pages 2006–2011. Springer New York, 2016

    work page 2006

  3. [3]

    Woodruff, and Samson Zhou

    Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, and Samson Zhou. Nearly optimal distinct elements and heavy hitters on sliding windows. InApproxima- tion, Randomization, and Combinatorial Optimization. Algorithms and Techniques (AP- PROX/RANDOM 2018), pages 7:1–7:22, 2018

    work page 2018

  4. [4]

    Smooth histograms for sliding windows

    Vladimir Braverman and Rafail Ostrovsky. Smooth histograms for sliding windows. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 283–293. IEEE, 2007

    work page 2007

  5. [5]

    Maintaining stream statistics over sliding windows.SIAM Journal on Computing, 31(6):1794–1813, 2002

    Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Maintaining stream statistics over sliding windows.SIAM Journal on Computing, 31(6):1794–1813, 2002

    work page 2002

  6. [6]

    Tight bounds for heavy hitters and moment estimation in the sliding window model

    Shiyuan Feng, William Swartworth, and David Woodruff. Tight bounds for heavy hitters and moment estimation in the sliding window model. InInternational Colloquium on Automata, Languages, and Programming (ICALP), 2025

    work page 2025

  7. [7]

    Gibbons and Srikanta Tirthapura

    Phillip B. Gibbons and Srikanta Tirthapura. Distributed streams algorithms for sliding windows. InProceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 63–72, 2002

    work page 2002

  8. [8]

    Almost-smooth histograms and sliding-window graph algorithms.Algorithmica, 84(10):2926–2953, 2022

    Robert Krauthgamer and David Reitblat. Almost-smooth histograms and sliding-window graph algorithms.Algorithmica, 84(10):2926–2953, 2022

    work page 2022

  9. [9]

    Muthukrishnan.Data Streams: Algorithms and Applications

    S. Muthukrishnan.Data Streams: Algorithms and Applications. Now Publishers Inc, 2005. 11

    work page 2005