কনটেন্টে যান

005 — Maximum Subarray

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

Problem link ও উৎস

  • Original source: Classic array/DP exercise (Kadane's algorithm)
  • Platform: LeetCode — https://leetcode.com/problems/maximum-subarray/
  • 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 করা

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

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

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

উদাহরণ
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
সবচেয়ে বড় যোগফলওয়ালা অংশ: [4, -1, 2, 1] -> যোগফল 6

Input ও output

উদাহরণ
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   (সবচেয়ে কম খারাপ একটা)

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

ভাবো তুমি দিন-দিন লাভ/ক্ষতির হিসাব রাখছ। প্রতিদিন জিজ্ঞেস করো: "আজ পর্যন্ত টানা চললে আমার সবচেয়ে ভালো streak কত?" যদি গতকাল পর্যন্ত তোমার মোট negative হয়ে যায়, তাহলে পুরোনো streak-টা ফেলে আজ থেকে নতুন গোনা শুরু করো — পুরোনো দেনা টেনে নিয়ে লাভ নেই। সাথে আলাদা করে "এ যাবৎ সেরা streak" মনে রাখো।

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

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

ভিত্তি হলো running sum (folder 02 — arrays)। কিন্তু এখানে মোচড়টা DP-র: প্রতিটা index-এ জিজ্ঞেস করি "এই element-এ শেষ হওয়া সবচেয়ে বড় subarray-র যোগফল কত?" এই "ends-at-i" anchor-টাই Kadane's algorithm-কে একটা পরিষ্কার DP-তে পরিণত করে।

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

লুকানো logic একটা সহজ সিদ্ধান্ত: index i-তে শেষ হওয়া best subarray হয় শুধু nums[i] একা, নয় আগের best subarray (যা i-1-এ শেষ) + nums[i]। অর্থাৎ — পেছনের যোগফল যদি negative হয়, সেটা টেনে আনার মানে নেই; নতুন করে এখান থেকে শুরু করাই ভালো।

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

সরাসরি কোনো বড় structure লাগে না — শুধু একটা চলমান সংখ্যা (i-তে শেষ হওয়া best sum) আর একটা global best। চাইলে একটা dp array রাখা যায় বোঝার জন্য, কিন্তু optimized version-এ দুটো variable যথেষ্ট।

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

State এখানে "ঠিক index i-তে শেষ হওয়া best subarray-র যোগফল" — একটামাত্র সংখ্যা। যেহেতু dp[i] শুধু dp[i-1] পড়ে, পুরো array লাগে না; একটা rolling variable-এ চলে। আর সত্যিকারের উত্তরটা সব dp[i]-এর মধ্যে সবচেয়ে বড়, তাই আলাদা একটা best variable রাখি।

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

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

প্রথম সরল চিন্তা: প্রতিটা সম্ভাব্য (start, end) জোড়ার subarray-র যোগফল গুনে, সবচেয়ে বড়টা রাখা।

উদাহরণ
best = -infinity
for start in 0..n-1:
    for end in start..n-1:
        s = sum(nums[start..end])
        best = max(best, s)

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

সব জোড়া ধরলে O(n^2) জোড়া, প্রতিটার যোগফল আবার গুনলে O(n^3); running sum দিয়ে O(n^2)। কিন্তু এতে অনেক repeated কাজ — একই prefix বারবার যোগ করা। বড় array-তে এটা ধীর; DP দিয়ে এক পাসে O(n)-এ নামানো যায়।

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

মূল observation: পুরো array-র best subarray কোনো না কোনো index-এ শেষ হবেই। তাই যদি প্রতিটা index-এ "এখানে শেষ হওয়া best subarray sum" জানি, তাহলে তাদের সবচেয়ে বড়টাই উত্তর। আর "এখানে শেষ হওয়া best" পেছনের best থেকে এক ধাপে পাওয়া যায়।

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

State (শব্দে): dp[i] = ঠিক index i-তে শেষ হওয়া contiguous subarray-গুলোর মধ্যে সবচেয়ে বড় যোগফল।

Transition:

উদাহরণ
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)।

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

মোচড়: "কোন subarray সবচেয়ে ভালো" খোঁজার বদলে প্রশ্নটা সংকীর্ণ করো — "প্রতিটা শেষ-বিন্দুর জন্য best কত?" এই "ends-at-i" anchor-ই মূল চাবি: এটা ছাড়া state-এ যথেষ্ট information থাকে না (LIS-এও একই শিক্ষা)। Anchor করলে transition নিজে নিজেই বেরিয়ে আসে।

ছবিতে বোঝা

dp[i] = ঠিক i-তে শেষ হওয়া best subarray sum। nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

উদাহরণ
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-এ ধাপে ধাপে

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

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

Python

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

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

  • 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 মিলিয়ে দেখা

cases-এ ছয়টা input: classic example, single element, সব-positive, single negative, all-negative, আর একটা mixed। প্রতিটার জন্য দুই function-ই মিলতে হবে। লক্ষ্য করো all-negative case-গুলো — উত্তর সবচেয়ে কম-খারাপ একটা element, কারণ অন্তত একটা নিতেই হয়। সব pass হলে শেষে print: সব test pass!।

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

সময়

দুই version-ই O(n) — array-র উপর একবার পাস। (Brute force ছিল O(n^2) বা O(n^3)।)

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

  • Tabulation: O(n) — dp array।
  • Kadane (fast): O(1) — দুটো variable।

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

  • 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 কখনো ফেলা হয় না, "নতুন শুরু" করার সুযোগ হারায়।

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

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

ভিত্তি: arrays-এর running sum (folder 02), আর "ends-at-i" anchoring — যেটা LIS-এও কেন্দ্রীয়। ../state-transition-thinking.md-এর LIS section-এ এই anchor-এর শিক্ষাটা গভীরভাবে আছে; এখানে সেই একই ধারণা contiguous sum-এ।

পরের অনুশীলন

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

Ends-at-i DP (Kadane): state-কে "ঠিক index i-তে শেষ হওয়া best" দিয়ে anchor করো, transition "নতুন শুরু vs আগেরটা extend"-এর max, উত্তর সব state-এর max। Anchor ছাড়া state অসম্পূর্ণ — এটাই এই family-র মূল শিক্ষা।

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

ভবিষ্যতের আমাকে: "Maximum Subarray = Kadane = ends-at-i DP।" State 'ঠিক i-তে শেষ হওয়া best sum', transition dp[i] = max(nums[i], dp[i-1]+nums[i]), উত্তর max(dp)। মনে রেখো: best nums[0] দিয়ে শুরু (all-negative trap), আর উত্তর শেষ cell নয় — সব cell-এর সর্বোচ্চ।

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