Approximate Maintenance of Maximum Subarray Sum in the Sliding Window Model
Ryo SuzukiYutaro Yamaguchi · 2026
Read Approximate Maintenance of Maximum Subarray Sum in the Sliding Window Model by Ryo SuzukiYutaro Yamaguchi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-23168.txt.
Introduction
Suzuki and Yamaguchi maintain the maximum subarray sum over the most recent n items of a data stream, where exact tracking usually needs space linear in n. Kadane's classic method fails here because each new item expires the oldest one, which can kill the best subarray found so far. A Smooth Histogram approach first yields a constant-factor approximation in squared-log space. Refining it, they reach any chosen accuracy in near-optimal space, with space cost shown asymptotically optimal.
Catalog record
| CREATOR | Ryo SuzukiYutaro Yamaguchi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31201 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.23168
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Approximate Maintenance of Maximum Subarray Sum in the Sliding Window Model Ryo SuzukiYutaro Yamaguchi Abstract In the sliding window model, we are required to maintain the target statistics over the most recent n n elements of a data stream, which is captured by a window of size n n sliding over the data stream. Exact computation usually requires space linear in n 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 ) O((\log n)^{2}) bits of space. We then refine this framework accordingly, which enables for any ϵ > 0 \epsilon>0 to maintain a ( 1 ± ϵ ) (1\pm\epsilon) -approximation using O ( ϵ − 1 ( log n ) 2 ) O(\epsilon^{-1}(\log n)^{2}) bits of space and O ( ϵ − 1 log n ) O(\epsilon^{-1}\log n) operations per update. The space complexity is asymptotically optimal. Keywords: Sliding window, Maximum subarray sum, Smooth histogram 1 Introduction The rapid growth of sequential data such as network logs, sensor measurements, and financial transactions has led to increasing interest in data stream processing. In many applications, only the most recent data is relevant for decision making, which motivates the sliding window model . In this model, at each time t , computations are performed on the most recent n elements, while older elements expire automatically. Maintaining statistics (e.g., mean, variance, and counting specific elements) is a typical task in the sliding window model. It is easy if we have plenty of time and memory, but becomes challenging under strict time or memory constraints. Storing all elements requires \Omega(n) space, which is impractical for large-scale streams. Therefore, the central goal is to maintain an approximation of the target statistics using sublinear space. For many problems in real-time applications, the time complexity of each update is also significant. 1.1 Sliding Window Model We formalize the sliding window model and the goal. Let (p_{1},p_{2},\dots) be a stream of data, and n be the window size . As a usual setting, we assume that all elements p_{i} are integers whose absolute values are bounded by O(\mathrm{poly}(n)) . At each time t=1,2,\dots , the active window is defined as \displaystyle W_{t}\coloneqq\begin{cases}(p_{1},p_{2},\dots,p_{t})&(t<n),\\ (p_{t-n+1},p_{t-n+2},\dots,p_{t})&(t\geq n).\end{cases} (1) Let f(W_{t}) denote the true value of the target statistics of W_{t} . Then, for \epsilon>0 , an estimation f^{\prime}(W_{t}) of f(W_{t}) is called a (1\pm\epsilon) -approximation if \displaystyle(1-\epsilon)f(W_{t})\leq f^{\prime}(W_{t})\leq(1+\epsilon)f(W_{t}). (2) An algorithm is also said to be (1\pm\epsilon) -approximation if at every time t it maintains a (1\pm\epsilon) -approximation of f(W_{t}) . The sliding window model was formally introduced by Datar, Gionis, Indyk, and Motwani [ 5 ] . They proposed the Exponential Histogram (EH) technique to maintain a certain type of statistics. As the simplest example, it shows that for any \epsilon>0 , a (1\pm\epsilon) -approximation of counting 1 s in the sliding window over a bit stream (where every p_{i} is 0 or 1 ) can be maintained only using O(\epsilon^{-1}(\log n)^{2}) bits of space (see Section 2.1 for more details). This work initiated a large body of research on sliding window algorithms (see, e.g., [ 2 , 9 ] ). While the EH technique can handle weakly additive functions efficiently, many important statistics fall outside this class. To address this limitation, Braverman and Ostrovsky [ 4 ] introduced the Smooth Histogram (SH) framework, which extends the applicability of sliding window algorithms to a broader class of functions satisfying a smoothness property (see Section 3 for the details). Subsequent work has further explored both the power and limitations of this framework. In particular, Krauthgamer and Reitblat [ 8 ] introduced the notion of almost-smooth functions, showing that the smooth histogram paradigm can be extended to functions that do not strictly satisfy smoothness, by relaxing the structural conditions. In addition, several works have improved space bounds for specific problems within the sliding window model. For example, Braverman, Grigorescu, Lang, Woodruff, and Zhou [ 3 ] established nearly optimal bounds for counting distinct elements and heavy hitters, showing that polylogarithmic space is both necessary and sufficient up to lower-order factors. More recently, Feng, Swartworth, Woodruff [ 6 ] further tightened these bounds by introducing the notion of strong estimators , which allow more flexible error guarantees while preserving high-probability correctness. Despite these advances, there remain fundamental limitations. Certain functions, such as inversion counting, exhibit strong global dependencies and do not satisfy smoothness-type properties. Indeed, small differences in the prefix discarded to save memory may lead to arbitrarily large deviations after future updates, making such functions unsuitable for SH-based approaches (see also [ 4 , 8 ] ). In parallel, alternative models and distributed variants of sliding window algorithms have also been studied [ 7 ] . 1.2 Maximum Subarray Sum In this paper, we study the problem of maintaining the maximum subarray sum in the sliding window model. Given a sequence W=(x_{1},x_{2},\dots,x_{n}) , the maximum subarray sum is defined as \displaystyle f(W)\coloneqq\max\left\{0,\max_{1\leq i\leq j\leq n}\sum_{k=i}^{j}x_{k}\right\}. (3) Note that when all the elements in W are nonpositive, so are the summations in ( 3 ), which is the only case that f(W)=0 . Besides, if x_{i}\in\{0,1\} for all i , then f(W) exactly counts 1s in W . Thus, if we restrict ourselves to the sliding window over a bit stream, this problem coincides with counting 1s. This problem has a long history and, according to Bentley [ 1 ] , originated in earlier work of Grenander on pattern analysis, first in a two-dimensional setting. It is also fundamental in the context of time series data, which captures local bursts, trends, and anomalies. In the static setting under the standard word RAM model, the problem admits a linear-time (moreover, constant-time per element) and constant-space solution via Kadane’s algorithm [ 1 ] (see Section 2.2 for the details). However, this approach cannot be directly extended to the sliding window model, since the expiration of elements may invalidate previously optimal subarrays. A naive solution requires \Theta(n) time per update and \Theta(n) space, which is impractical. 1.3 Our Contribution In this paper, we prove the following: Theorem 1.1 . For any \epsilon>0 , a (1\pm\epsilon) -approximation of the maximum subarray sum in the sliding window can be maintained using O(\epsilon^{-1}(\log n)^{2}) bits of space and O(\epsilon^{-1}\log n) operations per update. Our first observation is that the maximum subarray sum satisfies a relaxed smoothness condition. This observation enables a (1\pm\alpha) -approximation using O((\log n)^{2}) bits of space for a constant \alpha>\frac{1}{2} as a direct application of the standard SH framework. In order to achieve (1\pm\epsilon) -approximation for any \epsilon>0 , we need to refine it accordingly. In particular, by checking not only the maximum subarray sum but also the