011 — Maximum Subarray

Problem link ও উৎস

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

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

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

একটা 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

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

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

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

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

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

ভিত 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/।

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

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

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

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

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

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

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

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

প্রথম সরল চিন্তা: প্রতিটা শুরু-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)

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

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

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

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

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

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

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

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

ছবিতে বোঝা

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

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

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

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

Python

Python

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

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

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

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

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

JavaScript ও test cases

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

JavaScript

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।

TypeScript ও test cases

TypeScript

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 দিয়ে স্পষ্ট হয়।

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

সময়

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

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

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

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

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

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

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

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

পরের অনুশীলন

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

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

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

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

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

কোথায় কাজে লাগে

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