Problem link ও উৎস
- **Original source:** Classic array/DP exercise (Kadane's algorithm)
- **Platform:** LeetCode —
- **Topic:** dynamic programming
- **Difficulty:** Easy
- **Pattern:** 1D linear DP, "ends-at-i" anchor
- **Basic idea inherited from:** Arrays (folder 02) — running sum; এখানে DP দিয়ে Kadane derive করা
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা integer array দেওয়া আছে (negative সংখ্যাও থাকতে পারে)। তোমাকে এমন একটা **পরপর থাকা (contiguous)** অংশ বেছে নিতে হবে, যার যোগফল সবচেয়ে বড়। সেই সর্বোচ্চ যোগফলটা return করো। অংশটা অন্তত একটা element-এর হতে হবে।
```text
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
সবচেয়ে বড় যোগফলওয়ালা অংশ: [4, -1, 2, 1] -> যোগফল 6
```
### Input ও output {#8-example-input-and-output}
```text
Input : nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] -> Output: 6 (subarray [4,-1,2,1])
Input : nums = [1] -> Output: 1
Input : nums = [5, 4, -1, 7, 8] -> Output: 23
Edge case 1: nums = [-1] -> Output: -1 (সব negative, অন্তত একটা নিতেই হবে)
Edge case 2: nums = [-3, -1, -2] -> Output: -1 (সবচেয়ে কম খারাপ একটা)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি দিন-দিন লাভ/ক্ষতির হিসাব রাখছ। প্রতিদিন জিজ্ঞেস করো: "আজ পর্যন্ত টানা চললে আমার সবচেয়ে ভালো streak কত?" যদি গতকাল পর্যন্ত তোমার মোট negative হয়ে যায়, তাহলে পুরোনো streak-টা ফেলে আজ থেকে নতুন গোনা শুরু করো — পুরোনো দেনা টেনে নিয়ে লাভ নেই। সাথে আলাদা করে "এ যাবৎ সেরা streak" মনে রাখো।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি হলো **running sum** (folder 02 — arrays)। কিন্তু এখানে মোচড়টা DP-র: প্রতিটা index-এ জিজ্ঞেস করি "এই element-এ শেষ হওয়া সবচেয়ে বড় subarray-র যোগফল কত?" এই "ends-at-i" anchor-টাই Kadane's algorithm-কে একটা পরিষ্কার DP-তে পরিণত করে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা সহজ সিদ্ধান্ত: index `i`-তে শেষ হওয়া best subarray হয় **শুধু `nums[i]` একা**, নয় **আগের best subarray (যা `i-1`-এ শেষ) + `nums[i]`**। অর্থাৎ — পেছনের যোগফল যদি negative হয়, সেটা টেনে আনার মানে নেই; নতুন করে এখান থেকে শুরু করাই ভালো।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
সরাসরি কোনো বড় structure লাগে না — শুধু **একটা চলমান সংখ্যা** (`i`-তে শেষ হওয়া best sum) আর **একটা global best**। চাইলে একটা `dp` array রাখা যায় বোঝার জন্য, কিন্তু optimized version-এ দুটো variable যথেষ্ট।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
State এখানে "ঠিক index `i`-তে শেষ হওয়া best subarray-র যোগফল" — একটামাত্র সংখ্যা। যেহেতু `dp[i]` শুধু `dp[i-1]` পড়ে, পুরো array লাগে না; একটা rolling variable-এ চলে। আর সত্যিকারের উত্তরটা সব `dp[i]`-এর মধ্যে সবচেয়ে বড়, তাই আলাদা একটা `best` variable রাখি।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা সম্ভাব্য (start, end) জোড়ার subarray-র যোগফল গুনে, সবচেয়ে বড়টা রাখা।
```text
best = -infinity
for start in 0..n-1:
for end in start..n-1:
s = sum(nums[start..end])
best = max(best, s)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
সব জোড়া ধরলে **O(n^2)** জোড়া, প্রতিটার যোগফল আবার গুনলে **O(n^3)**; running sum দিয়ে O(n^2)। কিন্তু এতে অনেক repeated কাজ — একই prefix বারবার যোগ করা। বড় array-তে এটা ধীর; DP দিয়ে এক পাসে O(n)-এ নামানো যায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **পুরো array-র best subarray কোনো না কোনো index-এ শেষ হবেই।** তাই যদি প্রতিটা index-এ "এখানে শেষ হওয়া best subarray sum" জানি, তাহলে তাদের সবচেয়ে বড়টাই উত্তর। আর "এখানে শেষ হওয়া best" পেছনের best থেকে এক ধাপে পাওয়া যায়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
**State (শব্দে):** `dp[i]` = ঠিক index `i`-তে **শেষ হওয়া** contiguous subarray-গুলোর মধ্যে সবচেয়ে বড় যোগফল।
**Transition:**
```text
dp[i] = max( nums[i], # এখান থেকে নতুন শুরু
dp[i-1] + nums[i] ) # আগের best-কে বাড়াও
```
কারণ: `i`-তে শেষ হওয়া subarray হয় শুধু `nums[i]`, নয় `i-1`-এ শেষ হওয়া best-এর extension। পেছনের sum negative হলে নতুন শুরুই জেতে।
**Base case:** `dp[0] = nums[0]`।
**Answer location:** `max(dp[i])` সব `i`-এর উপর — `dp[n-1]` **নয়**, কারণ best subarray যেকোনো জায়গায় শেষ হতে পারে।
এটাই Kadane's algorithm। Memoization এখানে কম স্বাভাবিক (linear scan-ই natural), কিন্তু tabulation-এ পুরো `dp` array, আর O(1) version-এ দুটো variable (`cur`, `best`)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "কোন subarray সবচেয়ে ভালো" খোঁজার বদলে প্রশ্নটা সংকীর্ণ করো — "প্রতিটা শেষ-বিন্দুর জন্য best কত?" এই "ends-at-i" anchor-ই মূল চাবি: এটা ছাড়া state-এ যথেষ্ট information থাকে না (LIS-এও একই শিক্ষা)। Anchor করলে transition নিজে নিজেই বেরিয়ে আসে।
### ছবিতে বোঝা {#7-visual-explanation}
`dp[i]` = ঠিক `i`-তে শেষ হওয়া best subarray sum। `nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]`:
```text
i : 0 1 2 3 4 5 6 7 8
nums : -2 1 -3 4 -1 2 1 -5 4
dp[i] = max( nums[i], dp[i-1] + nums[i] )
dp[0] = -2 (একা)
dp[1] = max(1, -2+1) = max(1, -1) = 1 (পেছনের negative ফেলে দিল)
dp[2] = max(-3, 1-3) = max(-3,-2) = -2
dp[3] = max(4, -2+4) = max(4, 2) = 4 (আবার নতুন শুরু)
dp[4] = max(-1, 4-1) = max(-1,3) = 3
dp[5] = max(2, 3+2) = max(2, 5) = 5
dp[6] = max(1, 5+1) = max(1, 6) = 6 <- সর্বোচ্চ
dp[7] = max(-5, 6-5) = max(-5,1) = 1
dp[8] = max(4, 1+4) = max(4, 5) = 5
dp : -2 1 -2 4 3 5 6 1 5
best = max(dp) = 6
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`nums = [5, 4, -1, 7, 8]`, O(1) version (`cur` = `i`-তে শেষ best, `best` = global):
1. শুরু: `cur = 5`, `best = 5`
2. i=1: `cur = max(4, 5+4) = 9`; `best = max(5, 9) = 9`
3. i=2: `cur = max(-1, 9-1) = 8`; `best = max(9, 8) = 9`
4. i=3: `cur = max(7, 8+7) = 15`; `best = max(9, 15) = 15`
5. i=4: `cur = max(8, 15+8) = 23`; `best = max(15, 23) = 23`
6. return `best = 23`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
# ---- way 1: tabulation (bottom-up), full dp array ----
def max_subarray_tab(nums):
n = len(nums)
dp = [0] * n
dp[0] = nums[0] # base case
for i in range(1, n):
dp[i] = max(nums[i], dp[i - 1] + nums[i])
return max(dp) # answer যেকোনো জায়গায় শেষ হতে পারে
# ---- way 2: O(1) space (Kadane) ----
def max_subarray_fast(nums):
cur = nums[0] # i-তে শেষ হওয়া best
best = nums[0] # global best
for i in range(1, len(nums)):
cur = max(nums[i], cur + nums[i])
best = max(best, cur)
return best
# ---- tests ----
cases = [
([-2, 1, -3, 4, -1, 2, 1, -5, 4], 6),
([1], 1),
([5, 4, -1, 7, 8], 23),
([-1], -1),
([-3, -1, -2], -1),
([2, -1, 2, -1, 2], 4),
]
for nums, want in cases:
assert max_subarray_tab(nums) == want, (nums, max_subarray_tab(nums))
assert max_subarray_fast(nums) == want, (nums, max_subarray_fast(nums))
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `max_subarray_tab`: `dp[0] = nums[0]` base; loop প্রতি `i`-তে "নতুন শুরু" vs "extend" এর max নেয়; শেষে `max(dp)` — কারণ উত্তর শেষ cell-এ নাও থাকতে পারে।
- `max_subarray_fast`: `cur` হলো `dp[i]`-এর rolling রূপ, `best` সব `cur`-এর সর্বোচ্চ; পুরো array ছাড়াই এক পাসে কাজ শেষ।
- দুই version-এ একই recurrence, শুধু একটায় array রাখা, একটায় দুই variable।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`cases`-এ ছয়টা input: classic example, single element, সব-positive, single negative, all-negative, আর একটা mixed। প্রতিটার জন্য দুই function-ই মিলতে হবে। লক্ষ্য করো all-negative case-গুলো — উত্তর সবচেয়ে কম-খারাপ একটা element, কারণ অন্তত একটা নিতেই হয়। সব pass হলে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
দুই version-ই **O(n)** — array-র উপর একবার পাস। (Brute force ছিল O(n^2) বা O(n^3)।)
### অতিরিক্ত জায়গা {#19-space-complexity}
- Tabulation: **O(n)** — `dp` array।
- Kadane (fast): **O(1)** — দুটো variable।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `best` কে `0` দিয়ে initialize করা — তখন all-negative array-তে ভুল `0` ফেরত আসে; subarray অন্তত এক element, তাই `best = nums[0]` দিয়ে শুরু করো।
- উত্তর `dp[n-1]` return করা `max(dp)`-এর বদলে — best subarray যেকোনো জায়গায় শেষ হতে পারে।
- `cur = max(nums[i], cur + nums[i])`-এর বদলে `cur = cur + nums[i]` লেখা — তখন negative prefix কখনো ফেলা হয় না, "নতুন শুরু" করার সুযোগ হারায়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: arrays-এর running sum (folder 02), আর "ends-at-i" anchoring — যেটা LIS-এও কেন্দ্রীয়। [../state-transition-thinking.md](../state-transition-thinking.md)-এর LIS section-এ এই anchor-এর শিক্ষাটা গভীরভাবে আছে; এখানে সেই একই ধারণা contiguous sum-এ।
### পরের অনুশীলন {#22-similar-harder-problems}
- Maximum Product Subarray (sum-এর বদলে product, sign-এর জটিলতা) —