001 — Maximum Subarray¶

Source¶

Original source: Classic capstone interview problem (Kadane's algorithm)
Platform: LeetCode — https://leetcode.com/problems/maximum-subarray/
Topic: arrays + dynamic programming
Difficulty: Easy
Pattern: 1D DP (Kadane's running maximum)
Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 02 arrays (একবার array scan করা, contiguous subarray-র ধারণা) আর 12 dynamic programming (প্রতিটা index-এ একটা ছোট DP state রাখা)। দুই tool জোড়া লাগলেই Kadane।

1. Problem in simple words¶

তোমাকে একটা integer array দেওয়া আছে (negative number থাকতে পারে)। তোমার কাজ: এমন একটা পরপর থাকা (contiguous) টুকরো বেছে নাও, যার সব element যোগ করলে sum-টা সবচেয়ে বড় হয়। সেই সবচেয়ে বড় sum-টাই return করো — টুকরোটা না, শুধু তার যোগফল। টুকরোয় অন্তত একটা element থাকতেই হবে।

array : [-2, 1, -3, 4, -1, 2, 1, -5, 4]
সেরা টুকরো : [4, -1, 2, 1]  -> sum = 6

2. Which basic idea does this inherit from?¶

এই problem দুটো আগের chapter-এর tool জোড়া দেয়:

02 arrays থেকে: "contiguous subarray" মানেই array-র উপর একবার বাঁ-থেকে-ডান scan, আর কোন element কোথায় শুরু/শেষ হচ্ছে সেই thinking।
12 dynamic programming থেকে: প্রতিটা index-এ একটা ছোট sub-answer (এই index-এ শেষ হওয়া সেরা sum) রাখা, আর পরের সিদ্ধান্ত তার উপর দাঁড় করানো।

একা array scan তোমাকে দেয় সব টুকরো দেখার ক্ষমতা; একা DP দেয় sub-answer reuse করার ক্ষমতা। দুটো মিললে O(n)।

3. What is the hidden math or logic?¶

লুকানো logic একটা prefix decision: ধরো cur মানে "এই index-এ শেষ হওয়া সবচেয়ে বড় subarray sum"। প্রতিটা নতুন element x-এ মাত্র দুটো option —

হয় x-কে আগের টুকরোর সাথে জুড়ি: cur + x,
নয়তো x থেকে নতুন টুকরো শুরু করি: x।

বড়টা বেছে নিই: cur = max(x, cur + x)। এই একটামাত্র লাইনেই পুরো DP।

4. Which data structure is needed?¶

কোনো বড় data structure লাগে না — শুধু দুটো integer variable (cur, best)। এটাই Kadane-এর সৌন্দর্য: array (02) + DP (12) মিলেও extra memory O(1)।

5. Why this data structure fits¶

আমাদের পুরো DP table রাখার দরকার নেই, কারণ প্রতিটা step-এ আমরা শুধু আগের ঠিক একটা সংখ্যা (cur) ব্যবহার করি — পুরনো সব sub-answer না। এই "rolling DP" চিন্তা 12 dynamic programming-এর space-optimization trick, আর array (02)-র single-pass scan-এর সাথে নিখুঁত খাপ খায়। তাই দুটো variable-ই যথেষ্ট।

6. Real-life analogy¶

ভাবো তুমি দিনে দিনে লাভ-লোকসান হিসাব রাখছ। প্রতিদিন তুমি ঠিক করো: "আগের জমা পুঁজির সাথে আজকের হিসাব জুড়ব, নাকি আজ থেকে নতুন করে শুরু করব?" আগের পুঁজি যদি negative (টানছে নিচের দিকে) হয়, তুমি বরং fresh শুরু করো। সারা মাসের সবচেয়ে ভালো streak-টাই উত্তর।

7. Visual explanation¶

[-2, 1, -3, 4, -1, 2, 1] দিয়ে cur আর best-এর নাচ দেখি:

x = -2 :  cur = max(-2, None+-2) = -2     best = -2
x =  1 :  cur = max( 1,  -2+1)   =  1     best =  1
x = -3 :  cur = max(-3,   1+-3)  = -2     best =  1
x =  4 :  cur = max( 4,  -2+4)   =  4     best =  4   <- নতুন শুরু
x = -1 :  cur = max(-1,   4+-1)  =  3     best =  4
x =  2 :  cur = max( 2,   3+2)   =  5     best =  5
x =  1 :  cur = max( 1,   5+1)   =  6     best =  6   <- উত্তর

[4, -1, 2, 1] টুকরোটাই 6 দিল।

8. Example input and output¶

Input : [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6                       # [4, -1, 2, 1]

Edge case 1 (সব negative): Input: [-3, -1, -2]  -> Output: -1   # একটাই element নিতে হয়
Edge case 2 (একটা element): Input: [5]          -> Output: 5

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা সম্ভাব্য টুকরো (i থেকে j) ধরো, তার sum বের করো, সবচেয়ে বড়টা মনে রাখো।

for i in range(n):
    for j in range(i, n):
        s = sum(array[i..j])
        best = max(best, s)

10. Why brute force is slow¶

দুটো nested loop (i, j) দিয়ে সব pair, তার ভেতরে আবার sum — মোট O(n^3)। running sum রাখলে O(n^2)-এ নামে, কিন্তু তাও বড় array-তে ধীর। কারণ একই prefix-এর sum আমরা বারবার নতুন করে হিসাব করছি — এটাই DP (12) দূর করতে আসে।

11. Key observation¶

মূল observation: একটা ভালো টুকরো বাড়াতে গিয়ে যদি running sum কখনো negative হয়ে যায়, সেটা টেনে রাখার কোনো মানে নেই — পরের element-এর জন্য negative অতীত শুধু বোঝা। তখন অতীত ফেলে নতুন করে শুরু করাই ভালো। এই এক চিন্তাই O(n) এনে দেয়।

12. Optimized intuition¶

বাঁ থেকে ডান একবার হাঁটো। cur ধরে রাখে "এখানে শেষ হওয়া সেরা টুকরোর sum"। প্রতিটা element-এ ঠিক করো — অতীতের সাথে জুড়বে নাকি fresh শুরু করবে (max(x, cur+x))। পথে দেখা সবচেয়ে বড় cur-টাই best-এ জমাও। একবার পাস শেষ — উত্তর হাতে।

13. Thinking tweak¶

মোচড়: "সব টুকরো দেখব" ভাবার বদলে ভাবো "প্রতিটা index-এ শুধু একটা প্রশ্ন — negative অতীত ফেলে দেব কি না।" বিশাল 2D search একটা O(n) DP রোলে পরিণত হয়।

14. Step-by-step dry run¶

Input [-2, 1, -3, 4]:

শুরু: cur = -2, best = -2 (প্রথম element দিয়ে শুরু)
x = 1: cur = max(1, -2+1) = 1; best = max(-2, 1) = 1
x = -3: cur = max(-3, 1-3) = -2; best = max(1, -2) = 1
x = 4: cur = max(4, -2+4) = 4; best = max(1, 4) = 4
Loop শেষ → return best = 4 (টুকরো [4])

15. Python solution¶

def max_subarray(nums):
    cur = nums[0]               # এই index-এ শেষ হওয়া সেরা sum
    best = nums[0]              # সব মিলিয়ে সেরা sum
    for x in nums[1:]:
        cur = max(x, cur + x)   # অতীত ফেলব নাকি জুড়ব
        best = max(best, cur)   # পথের সেরা মনে রাখো
    return best

# ---- tests ----
assert max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
assert max_subarray([-3, -1, -2]) == -1     # সব negative
assert max_subarray([5]) == 5               # একটা element
assert max_subarray([1, 2, 3, 4]) == 10     # সব positive
assert max_subarray([-1, -2, -3, -4]) == -1 # সবচেয়ে কম negative
print("সব test pass!")

16. Line-by-line code explanation¶

cur = nums[0] — প্রথম element দিয়েই "এখানে শেষ হওয়া সেরা" শুরু; খালি টুকরো allowed না, তাই এটাই বেস।
best = nums[0] — global সেরাও প্রথম element দিয়ে শুরু (সব negative হলেও যেন সঠিক থাকে)।
for x in nums[1:] — দ্বিতীয় element থেকে একবার scan (02 arrays-এর single pass)।
cur = max(x, cur + x) — পুরো DP: অতীত negative হলে fresh শুরু, নাহলে জুড়ো।
best = max(best, cur) — যেহেতু সেরা টুকরো যেকোনো index-এ শেষ হতে পারে, প্রতি step-এ আপডেট।
return best — পুরো array দেখার পর সবচেয়ে বড় sum।

17. Output walkthrough¶

[-2, 1, -3, 4, -1, 2, 1, -5, 4]-এ scan করতে করতে cur এক সময় 4 -> 3 -> 5 -> 6 হয়ে ওঠে (টুকরো [4,-1,2,1]), তখন best হয় 6। শেষে -5 আর 4 আর সেটাকে ছাড়াতে পারে না, তাই return 6 — assert pass। সব-negative ও single-element case-ও সঠিক। শেষে print: সব test pass!।

18. Time complexity¶

O(n) — array-র উপর ঠিক একবার পাস, প্রতি element-এ O(1) কাজ।

19. Space complexity¶

O(1) — শুধু দুটো integer (cur, best); array-র সাইজের সাথে extra memory বাড়ে না (12 DP-র rolling-state trick)।

20. Common mistakes¶

best-কে 0 দিয়ে শুরু করা — সব-negative array-তে ভুল 0 দেয়; nums[0] দিয়ে শুরু করো।
cur-এ negative অতীত না ফেলা (শুধু cur += x করা) — তাহলে আর Kadane থাকে না।
খালি array আলাদা করে না ভাবা (nums[0] তখন crash করবে) — constraint বলে অন্তত একটা element আছে, তবু মনে রাখা ভালো।

21. Which basic problem this inherits from¶

ভিত্তি: array single-pass scan (02 arrays-এর ../../02-arrays-and-strings/) + প্রতি index-এ ছোট DP state রাখা (12 DP-র ../../12-dynamic-programming/patterns.md, 1D family)। এই দুটো cold অবস্থায় জানা থাকলে Kadane নিজে থেকেই বেরিয়ে আসে।

22. Similar harder problems¶

Maximum Product Subarray (negative দুটো মিলে positive হয়, তাই min+max দুটোই রাখতে হয়) — https://leetcode.com/problems/maximum-product-subarray/
Maximum Sum Circular Subarray — https://leetcode.com/problems/maximum-sum-circular-subarray/
Best Time to Buy and Sell Stock (একই running-min চিন্তা) — https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

23. Pattern learned¶

Kadane / rolling 1D DP: প্রতিটা index-এ একটা ছোট state (এখানে শেষ হওয়া সেরা) রেখে, "অতীত ফেলব নাকি জুড়ব" সিদ্ধান্ত নিয়ে O(n)-এ contiguous optimum বের করা। array + DP combo-র canonical রূপ।

24. Final summary¶

ভবিষ্যতের আমাকে: "contiguous + max/min sum" দেখলেই Kadane মনে করবে — দুটো variable, প্রতি element-এ max(x, cur+x), পথের সেরা জমাও। best-কে nums[0] দিয়ে শুরু করতে ভুলো না (সব-negative trap)। এটা array-scan আর 1D DP-র সবচেয়ে পরিষ্কার মেলবন্ধন।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।