Skip to content

005 — Maximum Subarray

Source

  • 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 করা

1. Problem in simple words

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

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

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 রাখি।

6. Real-life analogy

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

7. Visual explanation

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

8. Example input and 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   (সবচেয়ে কম খারাপ একটা)

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা সম্ভাব্য (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)

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:

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 নিজে নিজেই বেরিয়ে আসে।

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

15. Python solution

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

17. Output walkthrough

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

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

21. Which basic problem this inherits from

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

22. Similar harder problems

23. Pattern learned

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

24. Final summary

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