DEV Community

Cover image for From Brute Force to Kadane’s: Solving the Maximum Subarray Problem Efficiently
M Umair Ullah
M Umair Ullah

Posted on

From Brute Force to Kadane’s: Solving the Maximum Subarray Problem Efficiently

#dsa #programming #productivity #kadanealgo

🚀 Mastering Kadane's Algorithm: The Ultimate Guide to Maximum Subarray Sum

Kadane's Algorithm is one of the most elegant and widely asked Dynamic Programming techniques in coding interviews and DSA contests. If you're tackling problems involving maximum sum of contiguous subarrays, then this is a must-have in your toolbox.

💡 What is the Problem?

You're given an array of integers (which may contain both positive and negative numbers). You need to find the maximum sum of any contiguous subarray.

🧠 Real-World Analogy

Imagine you're tracking your profit/loss daily in a month. You want to find the most profitable streak of consecutive days. Some days might have loss (negative), some profit (positive), but you must find the contiguous stretch that gives you the maximum net gain.

📊 Example 

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Enter fullscreen mode Exit fullscreen mode

🔍 Step-by-Step Intuition

  • Start with a sum of 0 and a variable to track the maximum sum so far.
  • Iterate through each number:
  • Add it to your current sum.
  • If the current sum is greater than the max, update max.
  • If current sum becomes negative, reset it to 0 (because a negative sum won't help going forward).

🐢 Brute-Force Approach (Naive Method) 

cpp
// Time Complexity: O(n^2)
int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    int maxSum = INT_MIN;

    for (int i = 0; i < n; ++i) {
        int currSum = 0;
        for (int j = i; j < n; ++j) {
            currSum += nums[j];
            maxSum = max(maxSum, currSum);
        }
    }

    return maxSum;
}
Enter fullscreen mode Exit fullscreen mode

❌ Inefficient for large arrays.
✅ Good for understanding the concept.

⚡ Optimized Approach: Kadane’s Algorithm 

cpp

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

int maxSubArray(vector<int>& nums) {
    int currSum = 0, maxSum = INT_MIN;

    for (int i = 0; i < nums.size(); i++) {
        currSum += nums[i];
        maxSum = max(maxSum, currSum);

        if (currSum < 0)
            currSum = 0;
    }

    return maxSum;
}
Enter fullscreen mode Exit fullscreen mode

🧪 Practice Examples 

Try running the algorithm on:

nums = [5,4,-1,7,8] → Output: 23

nums = [-1,-2,-3,-4] → Output: -1

nums = [1] → Output: 1

nums = [8, -19, 5, -4, 20] → Output: 21
Enter fullscreen mode Exit fullscreen mode

🔁 Related LeetCode Problems to Practice

** Problem**

  • Maximum Subarray
  • Maximum Product Subarray
  • Maximum Sum Circular Subarray
  • Contiguous Array

💼 Add It to Your Portfolio

This is one of the most interview-favorite problems asked by:

  • Google
  • Amazon
  • Microsoft
  • Netflix
  • Adobe

💻 Open Source GitHub Solutions

🔗 Check out my full Kadane’s Algorithm solution with explanations here:
👉 GitHub Repository

✨ Wrapping Up

Kadane’s Algorithm is your go-to solution when you're dealing with subarrays and maximum sums. It’s blazing fast (O(n)), elegant, and powerful. Practice the problems, understand the variations, and you'll master it in no time!

Top comments (0)