011 — Maximum Subarray

Source

• Original source: Classic Kadane's algorithm exercise
• Platform: LeetCode — https://leetcode.com/problems/maximum-subarray/
• Topic: array / dynamic programming
• Difficulty: Medium
• Pattern: Kadane's algorithm (best ending here vs best so far)
• Basic idea inherited from: prefix sums — best subarray = prefix[j] - min(prefix[0..j-1]), আর Kadane সেই minimum-টাই implicitly track করে

1. Problem in simple words

একটা integer array nums দেওয়া (positive, negative দুটোই থাকতে পারে)। এমন একটা পরপর থাকা (contiguous) subarray খুঁজে বের করো যার element-গুলোর যোগফল সবচেয়ে বড়। তোমাকে সেই সবচেয়ে বড় যোগফল-টা ফেরত দিতে হবে। subarray-তে অন্তত একটা element থাকতে হবে।

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
সেরা subarray: [4, -1, 2, 1]  ->  যোগফল 6

2. Which basic idea does this inherit from?

ভিত prefix sums: index j-তে শেষ হওয়া সেরা subarray-র যোগফল = prefix[j] - min(prefix[0..j-1])। অর্থাৎ আগের সবচেয়ে ছোট prefix বিয়োগ করলে সবচেয়ে বড় অংশ পাওয়া যায়। Kadane এই minimum-টাকে আলাদা না রেখে চলমানভাবে track করে। গভীর derivation: ../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/।

3. What is the hidden math or logic?

লুকানো logic একটা ছোট recurrence: cur = max(x, cur + x)। মানে এই element-এ এসে দুটো পথের সেরাটা বাছো — হয় আগের run-টা extend করো (cur + x), নয়তো এখান থেকে fresh শুরু করো (x)। তারপর best = max(best, cur)। key অন্তর্দৃষ্টি: আগের running total negative হলে সেটা সামনের সবাইকে শুধু টেনে নামাবে, তাই ফেলে দাও।

4. Which data structure is needed?

কোনো data structure লাগে না — শুধু দুটো scalar variable: cur (current index-এ শেষ হওয়া সেরা subarray sum) আর best (এ যাবৎ দেখা সেরা sum)। O(1) extra space।

5. Why this data structure fits

পুরো prefix array বা সব subarray জমিয়ে রাখার দরকার নেই — যেকোনো index-এ সিদ্ধান্ত নিতে শুধু "এখানে শেষ হওয়া সেরা run কত" দরকার, যা একটা variable-এ ধরে রাখা যায়। array-র O(1) sequential read + দুটো variable update = সবচেয়ে হালকা সমাধান।

6. Real-life analogy

ভাবো তুমি প্রতিদিনের লাভ-ক্ষতি একটা খাতায় টুকছ। আজ পর্যন্ত চলমান হিসাব যদি ঋণাত্মক হয়ে যায়, সেটা টেনে রাখার কোনো মানে নেই — আজ থেকে নতুন করে হিসাব শুরু করো। সাথে আলাদা করে "এ যাবৎ সেরা streak কত ছিল" মনে রেখে দাও।

7. Visual explanation

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

x=-2: cur = -2                 best = -2
x= 1: cur = max(1, -2+1) = 1   best = 1     (restart)
x=-3: cur = 1-3 = -2           best = 1
x= 4: cur = max(4, -2+4) = 4   best = 4     (restart)
x=-1: cur = 4-1 = 3            best = 4
x= 2: cur = 3+2 = 5            best = 5
x= 1: cur = 5+1 = 6            best = 6  <- [4,-1,2,1]
x=-5: cur = 6-5 = 1            best = 6
x= 4: cur = 1+4 = 5            best = 6
answer: 6

8. Example input and output

Input : [-2, 1, -3, 4, -1, 2, 1, -5, 4] -> 6   ([4,-1,2,1])
Input : [1]                              -> 1
Input : [5, 4, -1, 7, 8]                 -> 23  (পুরোটা)

Edge case (সব negative): [-1, -2, -3]    -> -1  (সবচেয়ে বড় একটা element)

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা শুরু-index i থেকে প্রতিটা শেষ-index j পর্যন্ত subarray-র যোগফল হিসাব করে সবচেয়ে বড়টা রাখো।

best = -inf
for i in range(n):
    s = 0
    for j in range(i, n):
        s += nums[j]
        best = max(best, s)

10. Why brute force is slow

দুটো nested loop মানে O(n^2) subarray। বারবার একই overlap যোগ হচ্ছে — i fix রেখে j বাড়ালে যে কাজটা হয়, পরের i-তে আবার অনেকটা পুনরাবৃত্তি হয়। অথচ এক pass-এ "এখানে শেষ হওয়া সেরা run" রাখলেই সব কভার হয়।

11. Key observation

মূল observation: একটা index-এ শেষ হওয়া সেরা subarray হয় ঠিক আগের index-এ শেষ হওয়া সেরা run-এর extension, নয়তো এই element একা। তাই আগের run negative হলে তা টেনে রাখা বোকামি — fresh শুরু করাই ভালো। প্রতিটা element-এ এই একটাই local সিদ্ধান্ত global উত্তর দিয়ে দেয়।

12. Optimized intuition

cur আর best দুটোকেই প্রথম element দিয়ে শুরু করো। তারপর বাকি প্রতিটা x-এ: cur = max(x, cur + x) (extend নাকি restart), তারপর best = max(best, cur)। শেষে best-ই উত্তর। এক pass, O(n)।

13. Thinking tweak

মোচড়: "সব subarray-র যোগফল try করব" (O(n^2)) ভুলে গিয়ে ভাবো "চলমান run negative হলে ফেলে দেব, নাহলে টেনে নেব।" এই একটাই greedy সিদ্ধান্ত পুরো ভেতরের loop মুছে দেয়।

14. Step-by-step dry run

Input [-1, -2, -3] (সব negative):

1. শুরু: cur = -1, best = -1।
2. x=-2: cur = max(-2, -1+-2) = max(-2, -3) = -2; best = max(-1, -2) = -1।
3. x=-3: cur = max(-3, -2+-3) = max(-3, -5) = -3; best = max(-1, -3) = -1।
4. ফল: best = -1 (সবচেয়ে কম ক্ষতির একটা element)।

15. Python solution

def max_subarray(nums):
    best = nums[0]               # এ যাবৎ সেরা subarray sum
    cur = nums[0]                # এখানে শেষ হওয়া সেরা subarray sum
    for x in nums[1:]:
        cur = max(x, cur + x)    # আগের run extend, নাকি fresh শুরু
        best = max(best, cur)
    return best

# ---- tests ----
assert max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6   # [4,-1,2,1]
assert max_subarray([1]) == 1
assert max_subarray([5, 4, -1, 7, 8]) == 23                 # পুরোটা
assert max_subarray([-1, -2, -3]) == -1                     # সব negative
print("সব test pass!")

16. Line-by-line code explanation

• best = nums[0] / cur = nums[0] — প্রথম element দিয়ে শুরু; খালি subarray অনুমোদিত নয় বলে 0 দিয়ে শুরু করা যাবে না (সব negative হলে ভুল হতো)।
• for x in nums[1:] — দ্বিতীয় element থেকে হাঁটা।
• cur = max(x, cur + x) — Kadane-এর হৃদয়: extend নাকি restart।
• best = max(best, cur) — এ যাবৎ সেরা update।
• return best — পুরো pass শেষে সবচেয়ে বড় subarray sum।

17. Output walkthrough

[-2,1,-3,4,-1,2,1,-5,4] → cur বাড়তে বাড়তে [4,-1,2,1]-এ 6, best=6, assert pass। [1] → loop চলে না, 1; [5,4,-1,7,8] → পুরোটা যোগ হয়ে 23; [-1,-2,-3] → সবচেয়ে বড় একক element -1। শেষে print: সব test pass!।

18. Time complexity

O(n) — array-তে একবার হাঁটা, প্রতিটা step-এ O(1) compare/update।

19. Space complexity

O(1) — শুধু দুটো scalar (cur, best); input ছাড়া extra memory লাগে না।

20. Common mistakes

• best = 0 দিয়ে শুরু করা — সব element negative হলে উত্তর 0 হয়ে যাবে, যা ভুল (অন্তত একটা element নিতে হবে)।
• cur = cur + x লিখে restart-এর option বাদ দেওয়া — তখন negative run ফেলে দেওয়া হয় না।
• subarray-র সীমানা (index) ফেরত দিতে গিয়ে গুলিয়ে ফেলা — এই variant শুধু sum চায়; সীমানা চাইলে cur restart হওয়ার মুহূর্তে start track করতে হয়।

21. Which basic problem this inherits from

ভিত্তি: prefix-sum চিন্তা (prefix[j] - min prefix) আর running-aggregate (Buy/Sell Stock #7-এর জমজ)। chapter-এর ../patterns.md-এর "Pattern 7 — Kadane's Algorithm" দেখো; অনেকের প্রথম DP recurrence-ও এটাই।

22. Similar harder problems

• Maximum Product Subarray (min EBONG max track করো) — https://leetcode.com/problems/maximum-product-subarray/
• Best Time to Buy and Sell Stock (running-min variant) — https://leetcode.com/problems/best-time-to-buy-and-sell-stock/ (#7)
• Maximum Sum Circular Subarray — https://leetcode.com/problems/maximum-sum-circular-subarray/

23. Pattern learned

Kadane's algorithm: "max contiguous sum" দেখলে প্রতিটা index-এ "extend নাকি restart" — negative running total greedily ফেলে দাও। O(n) time, O(1) space, DP-র সবচেয়ে সরল রূপ।

24. Final summary

ভবিষ্যতের আমাকে: "cur = max(x, cur+x), best = max(best, cur); negative run ফেলে দাও।" "largest contiguous sum / best segment" দেখলেই Kadane মনে করবে — O(n) time, O(1) space।

25. JavaScript solution (with test cases)

Kadane-এর সেই দুই-scalar recurrence JS-এ হুবহু এক — Math.max দিয়ে extend নাকি restart।

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// maximum contiguous subarray sum (Kadane)
function maxSubarray(nums) {
  let best = nums[0];                 // এ যাবৎ সেরা subarray sum
  let cur = nums[0];                  // এখানে শেষ হওয়া সেরা subarray sum
  for (let i = 1; i < nums.length; i++) {
    const x = nums[i];
    cur = Math.max(x, cur + x);       // আগের run extend, নাকি fresh শুরু
    best = Math.max(best, cur);
  }
  return best;
}
// ---- test cases (example + edge) ----
assert(maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) === 6, "mixed");   // [4,-1,2,1]
assert(maxSubarray([1]) === 1, "single");
assert(maxSubarray([5, 4, -1, 7, 8]) === 23, "all-positive");
assert(maxSubarray([-1, -2, -3]) === -1, "all-negative");              // edge
console.log("সব JS test pass!");

JS টীকা: best/cur দুটোকেই nums[0] দিয়ে শুরু করো — 0 দিয়ে শুরু করলে সব-negative array-তে ভুল 0 আসবে। JS-এ Math.max(a, b) Python-এর max-এর সমতুল্য; integer overflow নিয়ে এখানে ভাবতে হয় না কারণ JS number 64-bit float।

26. TypeScript solution (with test cases)

function maxSubarray(nums: number[]): number {
  if (nums.length === 0) throw new Error("empty input not allowed");
  let best: number = nums[0];
  let cur: number = nums[0];
  for (let i = 1; i < nums.length; i++) {
    const x: number = nums[i];
    cur = Math.max(x, cur + x);
    best = Math.max(best, cur);
  }
  return best;
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
expect(maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]), 6, "mixed");
expect(maxSubarray([1]), 1, "single");
expect(maxSubarray([-1, -2, -3]), -1, "all-negative");
console.log("সব TS test pass!");

TS টীকা: parameter number[] declare করায় ভুল করে string array পাস করলে compile-time-এ ধরা পড়ে; খালি array-র edge case-ও explicit guard দিয়ে স্পষ্ট হয়।

27. কোথায় কাজে লাগে (real-world use)

• Stock/finance analytics: কোনো সময়সীমায় সবচেয়ে লাভজনক টানা সময়কাল (best contiguous profit window) বের করা — daily P&L-এর উপর Kadane।
• Signal processing: noisy sensor stream-এ সবচেয়ে শক্তিশালী টানা segment (max-energy burst) খুঁজে নেওয়া।
• Genomics: DNA/protein sequence-এ স্কোর দেওয়া সবচেয়ে significant টানা region (maximal scoring segment) detect করা।
• Game/leaderboard: খেলোয়াড়ের সবচেয়ে ভালো টানা streak (consecutive net gain) হিসাব করা।
• Image processing: 2D Kadane-এ ছবির সবচেয়ে উজ্জ্বল rectangular region বের করা (brightness sum max)।
• A/B testing trends: metric delta series-এ সবচেয়ে ভালো টানা পর্ব চিহ্নিত করা।

মূল pattern: "running aggregate negative হলে ফেলে দাও" — যেখানেই সেরা টানা অংশ চাই, সেখানেই Kadane।

---

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