🔥 Kadane's Algorithm — The Power of Maximum Subarrays

*Used in Amazon, Google, Microsoft Interviews 🚀
*

Hey devs 👋
If you’ve ever struggled with finding the maximum sum of a subarray, this is the trick you were probably missing: Kadane’s Algorithm.

It’s not just smart.
It’s ✨ interview magic ✨ — used by FAANG companies and loved by competitive programmers.

**📌 What is Kadane's Algorithm?
**Kadane’s Algorithm is a dynamic programming approach used to find the maximum sum of a contiguous subarray in linear time.

_Example problem:
_
Given an array [-2,1,-3,4,-1,2,1,-5,4],
Find the subarray with the maximum sum.
Answer: [4, -1, 2, 1] with sum = 6

**⚙️ How does Kadane's Algorithm work?
**Kadane’s magic is this:
👉 At every index, decide:

Should I start a new subarray here?
Or continue the previous one?
You track two values:

currentSum: Max sum ending at the current index
maxSum: Global max across the array

int maxSum = nums[0];
int currentSum = nums[0];

for (int i = 1; i < nums.length; i++) {
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
}

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

Problem | Description
🔗 Maximum Subarray | Classic Kadane
🔗 Best Time to Buy and Sell Stock | Kadane twist
🔗 Maximum Sum Circular Subarray | Kadane x2
🔗 Maximum Product Subarray | With sign twist
🔗 Contiguous Array | Advanced variation

💡 When to Use Kadane's?
When you need to find maximum/minimum sum of contiguous elements
When the array has positive and negative numbers
In profit gain, sensor data analysis, pattern detection

If you like please subscribe for such more concept and follow me on linkedIn for quick learning: