Problem link ও উৎস
- **Original source:** Classic Kadane's algorithm exercise
- **Platform:** LeetCode —
- **Topic:** array / dynamic programming
- **Difficulty:** Medium
- **Pattern:** Kadane's algorithm (best ending here vs best so far)
- **Basic idea inherited from:** prefix sums — best subarray = `prefix[j] - min(prefix[0..j-1])`, আর Kadane সেই minimum-টাই implicitly track করে
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা integer array `nums` দেওয়া (positive, negative দুটোই থাকতে পারে)। এমন একটা **পরপর থাকা (contiguous) subarray** খুঁজে বের করো যার element-গুলোর যোগফল সবচেয়ে বড়। তোমাকে সেই সবচেয়ে বড় **যোগফল**-টা ফেরত দিতে হবে। subarray-তে অন্তত একটা element থাকতে হবে।
```text
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
সেরা subarray: [4, -1, 2, 1] -> যোগফল 6
```
### Input ও output {#8-example-input-and-output}
```text
Input : [-2, 1, -3, 4, -1, 2, 1, -5, 4] -> 6 ([4,-1,2,1])
Input : [1] -> 1
Input : [5, 4, -1, 7, 8] -> 23 (পুরোটা)
Edge case (সব negative): [-1, -2, -3] -> -1 (সবচেয়ে বড় একটা element)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি প্রতিদিনের লাভ-ক্ষতি একটা খাতায় টুকছ। আজ পর্যন্ত চলমান হিসাব যদি ঋণাত্মক হয়ে যায়, সেটা টেনে রাখার কোনো মানে নেই — আজ থেকে নতুন করে হিসাব শুরু করো। সাথে আলাদা করে "এ যাবৎ সেরা streak কত ছিল" মনে রেখে দাও।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত **prefix sums**: index `j`-তে শেষ হওয়া সেরা subarray-র যোগফল = `prefix[j] - min(prefix[0..j-1])`। অর্থাৎ আগের সবচেয়ে ছোট prefix বিয়োগ করলে সবচেয়ে বড় অংশ পাওয়া যায়। Kadane এই minimum-টাকে আলাদা না রেখে চলমানভাবে track করে। গভীর derivation: [../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা ছোট recurrence: `cur = max(x, cur + x)`। মানে এই element-এ এসে দুটো পথের সেরাটা বাছো — হয় আগের run-টা extend করো (`cur + x`), নয়তো এখান থেকে fresh শুরু করো (`x`)। তারপর `best = max(best, cur)`। key অন্তর্দৃষ্টি: আগের running total negative হলে সেটা সামনের সবাইকে শুধু টেনে নামাবে, তাই ফেলে দাও।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো data structure লাগে না — শুধু **দুটো scalar variable**: `cur` (current index-এ শেষ হওয়া সেরা subarray sum) আর `best` (এ যাবৎ দেখা সেরা sum)। O(1) extra space।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
পুরো prefix array বা সব subarray জমিয়ে রাখার দরকার নেই — যেকোনো index-এ সিদ্ধান্ত নিতে শুধু "এখানে শেষ হওয়া সেরা run কত" দরকার, যা একটা variable-এ ধরে রাখা যায়। array-র O(1) sequential read + দুটো variable update = সবচেয়ে হালকা সমাধান।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা শুরু-index `i` থেকে প্রতিটা শেষ-index `j` পর্যন্ত subarray-র যোগফল হিসাব করে সবচেয়ে বড়টা রাখো।
```text
best = -inf
for i in range(n):
s = 0
for j in range(i, n):
s += nums[j]
best = max(best, s)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
দুটো nested loop মানে **O(n^2)** subarray। বারবার একই overlap যোগ হচ্ছে — `i` fix রেখে `j` বাড়ালে যে কাজটা হয়, পরের `i`-তে আবার অনেকটা পুনরাবৃত্তি হয়। অথচ এক pass-এ "এখানে শেষ হওয়া সেরা run" রাখলেই সব কভার হয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: একটা index-এ শেষ হওয়া সেরা subarray হয় ঠিক আগের index-এ শেষ হওয়া সেরা run-এর extension, নয়তো এই element একা। তাই আগের run negative হলে তা টেনে রাখা বোকামি — fresh শুরু করাই ভালো। প্রতিটা element-এ এই একটাই local সিদ্ধান্ত global উত্তর দিয়ে দেয়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`cur` আর `best` দুটোকেই প্রথম element দিয়ে শুরু করো। তারপর বাকি প্রতিটা `x`-এ: `cur = max(x, cur + x)` (extend নাকি restart), তারপর `best = max(best, cur)`। শেষে `best`-ই উত্তর। এক pass, O(n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব subarray-র যোগফল try করব" (O(n^2)) ভুলে গিয়ে ভাবো "চলমান run negative হলে ফেলে দেব, নাহলে টেনে নেব।" এই একটাই greedy সিদ্ধান্ত পুরো ভেতরের loop মুছে দেয়।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]`:
```text
x=-2: cur = -2 best = -2
x= 1: cur = max(1, -2+1) = 1 best = 1 (restart)
x=-3: cur = 1-3 = -2 best = 1
x= 4: cur = max(4, -2+4) = 4 best = 4 (restart)
x=-1: cur = 4-1 = 3 best = 4
x= 2: cur = 3+2 = 5 best = 5
x= 1: cur = 5+1 = 6 best = 6 <- [4,-1,2,1]
x=-5: cur = 6-5 = 1 best = 6
x= 4: cur = 1+4 = 5 best = 6
answer: 6
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[-1, -2, -3]` (সব negative):
1. শুরু: `cur = -1`, `best = -1`।
2. `x=-2`: `cur = max(-2, -1+-2) = max(-2, -3) = -2`; `best = max(-1, -2) = -1`।
3. `x=-3`: `cur = max(-3, -2+-3) = max(-3, -5) = -3`; `best = max(-1, -3) = -1`।
4. ফল: `best = -1` (সবচেয়ে কম ক্ষতির একটা element)।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def max_subarray(nums):
best = nums[0] # এ যাবৎ সেরা subarray sum
cur = nums[0] # এখানে শেষ হওয়া সেরা subarray sum
for x in nums[1:]:
cur = max(x, cur + x) # আগের run extend, নাকি fresh শুরু
best = max(best, cur)
return best
# ---- tests ----
assert max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6 # [4,-1,2,1]
assert max_subarray([1]) == 1
assert max_subarray([5, 4, -1, 7, 8]) == 23 # পুরোটা
assert max_subarray([-1, -2, -3]) == -1 # সব negative
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `best = nums[0]` / `cur = nums[0]` — প্রথম element দিয়ে শুরু; খালি subarray অনুমোদিত নয় বলে 0 দিয়ে শুরু করা যাবে না (সব negative হলে ভুল হতো)।
- `for x in nums[1:]` — দ্বিতীয় element থেকে হাঁটা।
- `cur = max(x, cur + x)` — Kadane-এর হৃদয়: extend নাকি restart।
- `best = max(best, cur)` — এ যাবৎ সেরা update।
- `return best` — পুরো pass শেষে সবচেয়ে বড় subarray sum।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[-2,1,-3,4,-1,2,1,-5,4]` → cur বাড়তে বাড়তে [4,-1,2,1]-এ 6, `best=6`, assert pass। `[1]` → loop চলে না, `1`; `[5,4,-1,7,8]` → পুরোটা যোগ হয়ে `23`; `[-1,-2,-3]` → সবচেয়ে বড় একক element `-1`। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
Kadane-এর সেই দুই-scalar recurrence JS-এ হুবহু এক — `Math.max` দিয়ে extend নাকি restart।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// maximum contiguous subarray sum (Kadane)
function maxSubarray(nums) {
let best = nums[0]; // এ যাবৎ সেরা subarray sum
let cur = nums[0]; // এখানে শেষ হওয়া সেরা subarray sum
for (let i = 1; i < nums.length; i++) {
const x = nums[i];
cur = Math.max(x, cur + x); // আগের run extend, নাকি fresh শুরু
best = Math.max(best, cur);
}
return best;
}
// ---- test cases (example + edge) ----
assert(maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) === 6, "mixed"); // [4,-1,2,1]
assert(maxSubarray([1]) === 1, "single");
assert(maxSubarray([5, 4, -1, 7, 8]) === 23, "all-positive");
assert(maxSubarray([-1, -2, -3]) === -1, "all-negative"); // edge
console.log("সব JS test pass!");
```
> **JS টীকা:** `best`/`cur` দুটোকেই `nums[0]` দিয়ে শুরু করো — `0` দিয়ে শুরু করলে সব-negative array-তে ভুল `0` আসবে। JS-এ `Math.max(a, b)` Python-এর `max`-এর সমতুল্য; integer overflow নিয়ে এখানে ভাবতে হয় না কারণ JS number 64-bit float।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function maxSubarray(nums: number[]): number {
if (nums.length === 0) throw new Error("empty input not allowed");
let best: number = nums[0];
let cur: number = nums[0];
for (let i = 1; i < nums.length; i++) {
const x: number = nums[i];
cur = Math.max(x, cur + x);
best = Math.max(best, cur);
}
return best;
}
function expect