1.6 Kadane's Algorithm

Demo: Maximum Subarray — LC 53 (Medium)

Statement (Demo): integer array nums দেওয়া — সবচেয়ে বড় যোগফল সম্পন্ন contiguous subarray খুঁজে বের করুন এবং সেই যোগফল return করুন। উদাহরণ: [-2,1,-3,4,-1,2,1,-5,4] → 6 | ⚡ n ≤ 10⁵, -10⁴ ≤ nums[i] ≤ 10⁴

Approach: প্রতিটা index-এ সিদ্ধান্ত — আগের চলমান sum positive contribution দিলে যোগ করুন, নাহলে এখান থেকে নতুন subarray শুরু। global best আলাদা রাখুন।

function maxSubArray(nums) {
  let cur = nums[0],
    best = nums[0];
  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]); // নতুন শুরু vs টেনে নেওয়া
    best = Math.max(best, cur);
  }
  return best;
}

Complexity: Time O(n), Space O(1)