কনটেন্টে যান

001 — Maximum Subarray

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

  • 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।

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

তোমাকে একটা 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

Input ও 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

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এই 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)।

ভেতরের যুক্তি

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

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

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

কী দিয়ে তথ্য রাখব

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

এটি কেন উপযুক্ত

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

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

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

উদাহরণ
for i in range(n):
    for j in range(i, n):
        s = sum(array[i..j])
        best = max(best, s)

কোথায় বেশি কাজ হচ্ছে

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

যে বিষয়টি খেয়াল করতে হবে

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

আরও কম কাজে সমাধান

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

ভাবনার পরিবর্তন

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

ছবিতে বোঝা

[-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 দিল।

ছোট input-এ ধাপে ধাপে

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

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

কোড ও ব্যাখ্যা

Python

Python
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!")

কোডের প্রতিটি অংশ

  • 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।

Output মিলিয়ে দেখা

[-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!।

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

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

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

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

পরের অনুশীলন

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "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।