Problem link ও উৎস
- **Original source:** Classic exercise (fixed-size sliding window)
- **Platform:** Classic exercise —
- **Topic:** Sliding window → fixed-size window, incremental sum
- **Difficulty:** Easy
- **Pattern:** fixed window (একটা ঢোকে, একটা বেরোয়)
- **Basic idea inherited from:** 067 — Prefix Sum (running sum ধরে রাখা; window হলো তার চলমান রূপ)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা array `a` আর একটা সংখ্যা `k` দেওয়া। ঠিক `k` টা পরপর element নিয়ে যে subarray হয় তাদের যোগফলের মধ্যে **সর্বোচ্চ** যোগফলটা বের করো (চাইলে সব window-র sum-ও বের করা যায়)।
মানে array-র উপর `k` দৈর্ঘ্যের একটা জানালা বসিয়ে এক ঘর করে ডানে সরাতে থাকো; প্রতিবার window-র ভেতরের যোগফল দেখো, সর্বোচ্চটা রাখো।
### Input ও output {#6-example-input-and-output}
```text
a k -> max window sum (কোন window)
-----------------------------------------------------------
[2, 1, 5, 1, 3, 2] 3 -> 9 [5, 1, 3]
[1, 2, 3, 4, 5] 2 -> 9 [4, 5]
[5, 5, 5] 3 -> 15 পুরোটাই
[2, 3] 2 -> 5 [2, 3]
[-1, -2, -3, -4] 2 -> -3 [-1, -2]
[4] 1 -> 4 [4]
```
Edge case: `k == len(a)` হলে একটাই window (পুরো array); negative থাকলেও কাজ করে (sum যেমন তেমন)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা চলন্ত ট্রেনের ঠিক `k` টা বগি তুমি জানালা দিয়ে দেখছ। ট্রেন এক বগি এগোলে — সামনের একটা নতুন বগি দৃশ্যে ঢোকে, পেছনের একটা বেরিয়ে যায়। মাঝের `k−2` টা বগি একই থাকে।
এখন যদি প্রতিটা বগির ওজন যোগ করতে চাও, তুমি কি প্রতিবার সব `k` বগি আবার গুনবে? না — আগের যোগফল থেকে যেটা বেরোল তার ওজন বাদ দাও, যেটা ঢুকল তার ওজন যোগ করো। এক বিয়োগ, এক যোগ — ব্যস। এটাই sliding window-র মিতব্যয়িতা।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
**067 — Prefix Sum**-এর কাঁধে। Prefix sum-এ আমরা একটা running total ধরে রাখি আর দরকারে অংশ বের করি। Fixed window আসলে সেই running total-এর একটা **চলমান** রূপ — পুরো prefix না রেখে শুধু বর্তমান window-র sum ধরে রাখি, আর সরানোর সময় দুই প্রান্তে adjust করি।
আসলে fixed-window sum prefix sum দিয়েও লেখা যায়: `window_sum = prefix[r+1] − prefix[r+1−k]`। তাই 085 শেখায় — prefix-এর "running total" idea-টাই window-এর জন্ম দেয়, শুধু O(1) space-এ।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **incremental update** (টুকরো হিসাব হালনাগাদ)। দুটো পাশাপাশি window-র মধ্যে পার্থক্য মাত্র দুটো element — ডানে নতুন একটা ঢোকে, বাঁয়ে পুরোনো একটা বেরোয়। তাই:
```text
নতুন sum = পুরোনো sum + (যেটা ঢুকল) − (যেটা বেরোল)
```
পুরো `k` element আবার যোগ না করে এক বিয়োগ + এক যোগ — এটাই O(n·k)-কে O(n)-এ নামায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরল পথ — প্রতিটা window আলাদা করে পুরো যোগ করা:
```python
def max_window_sum_brute(a, k):
n = len(a)
best = None
for start in range(n - k + 1):
s = sum(a[start:start + k]) # প্রতিবার নতুন করে k টা যোগ
if best is None or s > best:
best = s
return best
```
ঠিক উত্তর দেয় — প্রতিটা window-র sum স্বাধীনভাবে গুনে সর্বোচ্চটা রাখে।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
window সংখ্যা প্রায় `n − k`, প্রতিটার জন্য `k` বার যোগ → মোট প্রায় `n·k` operation। `n = 100000, k = 50000` হলে প্রায় ৫০০ কোটি — Time Limit Exceeded।
```text
n = 100000, k = 50000:
brute force : ~5,000,000,000 যোগ (O(n·k))
sliding window: ~100000 step (O(n))
```
মূল অপচয়: পাশাপাশি দুই window-র মাঝে শুধু দুটো element বদলায়, তবু brute force প্রতিবার সব `k` টা আবার যোগ করছে — একই কাজ বারবার।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: **পাশের window-এ যাওয়া মানে এক বিয়োগ + এক যোগ — পুরোটা আবার গুনতে হয় না।**
```text
প্রথম window-র sum একবার গোনো: s = sum(a[0:k])
তারপর প্রতি ঘর ডানে সরায়:
s += a[r] - a[r - k] # নতুনটা যোগ, k ঘর আগেরটা বিয়োগ
best = max(best, s)
```
এক pass-এ সব window-র sum পাওয়া যায়, প্রতিটা O(1) update।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!": **window সরানো = নতুনটা যোগ করো, যেটা পড়ে গেল সেটা বিয়োগ করো — মাঝেরগুলো ছোঁয়ারই দরকার নেই।**
মূল কাজ একটাই লাইন: `s += a[r] - a[r-k]`। এই এক লাইনই O(n·k)-কে O(n)-এ নামায়। আর এই "একটা ঢোকে, একটা বেরোয়" idea-ই variable window-র (086, 087) দিকে দরজা খোলে।
### ছবিতে বোঝা {#5-visual-explanation}
`a = [2, 1, 5, 1, 3, 2]`, `k = 3` — জানালা ডানে হাঁটছে:
```text
a = [ 2 , 1 , 5 , 1 , 3 , 2 ]
window 1: [ 2 1 5 ] 1 3 2 sum = 2+1+5 = 8
window 2: 2 [ 1 5 1 ] 3 2 sum = 8 + 1 - 2 = 7 (1 ঢুকল, 2 বেরোল)
window 3: 2 1 [ 5 1 3 ] 2 sum = 7 + 3 - 1 = 9 (3 ঢুকল, 1 বেরোল)
window 4: 2 1 5 [ 1 3 2 ] sum = 9 + 2 - 5 = 6 (2 ঢুকল, 5 বেরোল)
সর্বোচ্চ = 9
```
প্রতিবার পুরো জানালা গুনিনি — শুধু দুই প্রান্তে adjust:
```text
[#####] . . . পুরোনো sum
[#####] . . +নতুন(ডান) −পুরোনো(বাঁ)
[#####] . আবার +নতুন −পুরোনো
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`a = [2, 1, 5, 1, 3, 2]`, `k = 3`। প্রথমে `s = sum(a[0:3]) = 8`, `best = 8`:
| r | a[r] (ঢোকে) | a[r-k] (বেরোয়) | s = s + ঢোকে − বেরোয় | best |
| --- | --- | --- | --- | --- |
| (শুরু) | — | — | 2+1+5 = 8 | 8 |
| 3 | a[3]=1 | a[0]=2 | 8 + 1 − 2 = 7 | 8 |
| 4 | a[4]=3 | a[1]=1 | 7 + 3 − 1 = 9 | 9 |
| 5 | a[5]=2 | a[2]=5 | 9 + 2 − 5 = 6 | 9 |
সর্বোচ্চ **9** (`[5, 1, 3]`)। লক্ষ করো প্রতি step-এ মাত্র একটা যোগ + একটা বিয়োগ — মাঝের element কখনো আবার গোনা হয়নি।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def max_window_sum(a, k):
"""ঠিক k দৈর্ঘ্যের window-গুলোর সর্বোচ্চ sum ফেরত দেয় (1 <= k <= len(a))।"""
s = sum(a[:k])
best = s
for r in range(k, len(a)):
s += a[r] - a[r - k] # নতুনটা যোগ, পুরোনোটা বিয়োগ
if s > best:
best = s
return best
def window_sums(a, k):
"""প্রতিটা window-র sum-এর list (পরপর) ফেরত দেয় — দেখার জন্য।"""
s = sum(a[:k])
out = [s]
for r in range(k, len(a)):
s += a[r] - a[r - k]
out.append(s)
return out
def max_window_sum_brute(a, k):
"""ধীর reference — প্রতিটা window নতুন করে যোগ।"""
n = len(a)
best = None
for start in range(n - k + 1):
s = sum(a[start:start + k])
if best is None or s > best:
best = s
return best
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert max_window_sum([2, 1, 5, 1, 3, 2], 3) == 9
assert max_window_sum([1, 2, 3, 4, 5], 2) == 9
assert max_window_sum([5, 5, 5], 3) == 15
assert max_window_sum([2, 3], 2) == 5
assert max_window_sum([-1, -2, -3, -4], 2) == -3
assert max_window_sum([4], 1) == 4
assert window_sums([2, 1, 5, 1, 3, 2], 3) == [8, 7, 9, 6]
# brute force-এর সাথে মিলিয়ে দেখা (নানা random case)
import random
random.seed(17)
for _ in range(400):
n = random.randint(1, 12)
arr = [random.randint(-5, 5) for _ in range(n)]
k = random.randint(1, n)
assert max_window_sum(arr, k) == max_window_sum_brute(arr, k), (arr, k)
print(max_window_sum([2, 1, 5, 1, 3, 2], 3)) # 9
print(window_sums([2, 1, 5, 1, 3, 2], 3)) # [8, 7, 9, 6]
print(max_window_sum([1, 2, 3, 4, 5], 2)) # 9
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
s = sum(a[:k])
best = s
```
প্রথম window-র sum একবারই পুরো গোনা হয়; সেটাই শুরুর সেরা।
```text
for r in range(k, len(a)):
```
`r` হলো নতুন ঢোকা element-এর index; শুরু `k` থেকে কারণ প্রথম window `[0..k-1]` আগেই গোনা।
```text
s += a[r] - a[r - k]
```
হৃদয় — নতুন `a[r]` যোগ, ঠিক `k` ঘর আগের `a[r-k]` (যেটা window থেকে পড়ে গেল) বিয়োগ।
```text
if s > best: best = s
```
প্রতি window-র পর সেরাটা হালনাগাদ।
`window_sums` সব window-র sum দেখায়; `max_window_sum_brute` test যাচাইয়ের reference (random case-এ মিলিয়ে দেখা)।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
9
[8, 7, 9, 6]
9
সব test pass!
```
প্রথম লাইন সর্বোচ্চ window sum 9; দ্বিতীয় লাইন প্রতিটা window-র sum পরপর `[8, 7, 9, 6]`; তৃতীয় লাইন `[1..5]` k=2-এর সর্বোচ্চ 9 (`[4,5]`)। তার আগে 400 random case brute-force-এর সাথে মিলেছে, তাই `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n)** — প্রথম window O(k) একবার, এরপর প্রতিটা slide O(1) (এক যোগ + এক বিয়োগ), মোট প্রায় n বার। তাই O(k + n) = O(n)।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু `s`, `best` (max চাইলে)। (সব window-র sum list চাইলে O(n), কিন্তু শুধু সর্বোচ্চের জন্য বাড়তি জায়গা প্রায় শূন্য।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **প্রতি window পুরো আবার যোগ করা** — তখন O(n·k); incremental update-ই আসল লাভ।
- **`a[r - k]` বিয়োগ ভুলে যাওয়া** — শুধু যোগ করলে window বড় হতে থাকে, sum ভুল।
- **প্রথম window ভুলে loop শুরু করা** — `range(k, ...)` থেকে শুরু; প্রথম `[0..k-1]` আগে আলাদা করে গুনতে হয়।
- **`k > len(a)` না ভাবা** — তখন window-ই হয় না; বাস্তবে `1 <= k <= len(a)` ধরে নেওয়া বা আগে যাচাই।
- **negative element ভয় পাওয়া** — fixed window negative-এও দিব্যি চলে (sum যেমনই হোক); ভয়টা variable window-এ (086+)।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **GeeksforGeeks Window Sliding Technique** (