Algorithm-Day13-Maximum-Subarray-lc-53

Posted on In , Views:

🧩 Problem Description

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example:

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

💡 Brute Force (Too Slow)

Try all subarrays and calculate the sum:

  • Time complexity: O(n²) to O(n³)
  • ❌ Not acceptable for large inputs

💡 Optimal Approach: Kadane’s Algorithm

✨ Key Idea

At each position i, we decide:

  • Either start a new subarray at i, or
  • Extend the previous subarray to include nums[i]

This leads to the recurrence:

1
2
currentMax = max(nums[i], currentMax + nums[i])
globalMax = max(globalMax, currentMax)

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxSubArray(int[] nums) {
        int currentMax = nums[0];
        int globalMax = nums[0];

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

        return globalMax;
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n) – single pass
  • Space Complexity: O(1) – no extra array needed

✍️ Summary

  • Kadane’s Algorithm is a must-know for maximum subarray problems.
  • It tracks both the current streak and global maximum.
  • Often appears in interview problems and can be extended to 2D, circular arrays, etc.

If you understand this pattern, problems like “maximum profit”, “maximum product”, and “max subarray length” will feel much easier.