Approximate Maintenance of Maximum Subarray Sum in the Sliding Window Model
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914507508416512 |
|---|---|
| author | Suzuki, Ryo Yamaguchi, Yutaro |
| author_facet | Suzuki, Ryo Yamaguchi, Yutaro |
| contents | 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 $ε> 0$ to maintain a $(1 \pm ε)$-approximation using $O(ε^{-1}(\log n)^2)$ bits of space and $O(ε^{-1}\log n)$ operations per update. The space complexity is asymptotically optimal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_23168 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Approximate Maintenance of Maximum Subarray Sum in the Sliding Window Model Suzuki, Ryo Yamaguchi, Yutaro Data Structures and Algorithms 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 $ε> 0$ to maintain a $(1 \pm ε)$-approximation using $O(ε^{-1}(\log n)^2)$ bits of space and $O(ε^{-1}\log n)$ operations per update. The space complexity is asymptotically optimal. |
| title | Approximate Maintenance of Maximum Subarray Sum in the Sliding Window Model |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.23168 |