53. Maximum Subarray | Kadane’s Algorithm

53. Maximum Subarray

 Medium
Topics: Array, Dynamic Programming

💬 Problem Statement:

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

---

🧪 Examples:

Example 1:

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

Example 2:

Input: nums = [1]  
Output: 1  
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]  
Output: 23  
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

---

🔒 Constraints:

• 1 <= nums.length <= 10⁵

• -10⁴ <= nums[i] <= 10⁴

---

🧠 Approach 1: Kadane's Algorithm (O(n) Time)

Kadane’s Algorithm helps you find the maximum sum of a contiguous subarray in just one pass.

👉 Intuition:

We move through the array and:

• Keep adding elements to a running sum (maxEndingHere)

• If maxEndingHere becomes negative, we reset it to 0

• Track the maximum seen so far in maxSoFar
 

MY solution,
🪄 Java Code:

 

 class Solution {

    public int maxSubArray(int[] nums) {

        int currentSum = nums[0];

        int maxSum = nums[0];

        for (int i = 1; i < nums.length; i++) {

            // Either start a new subarray at nums[i], or extend the previous one

            currentSum = Math.max(nums[i], currentSum + nums[i]);

            maxSum = Math.max(maxSum, currentSum);

        }

        return maxSum;

    }

}

🪄 Java Code:

public class Solution {
    public int maxSubArray(int[] nums) {
        int maxSoFar = Integer.MIN_VALUE;
        int maxEndingHere = 0;
        for (int num : nums) {
            maxEndingHere += num;
            if (maxSoFar < maxEndingHere) {
                maxSoFar = maxEndingHere;
            }
            if (maxEndingHere < 0) {
                maxEndingHere = 0;
            }
        }
        return maxSoFar;
    }
}
 

import java.util.ArrayList;
class Solution {
    public int findMinDiff(ArrayList<Integer> arr, int m) {
        // If the number of packets is less than the number of students, return -1
        if (arr.size() < m) {
            return -1;
        }
        // Sort the array to bring similar values together
        arr.sort(null);
        int minDiff = Integer.MAX_VALUE;
        // Use a sliding window to find the minimum difference
        for (int i = 0; i + m - 1 < arr.size(); i++) {
            int diff = arr.get(i + m - 1) - arr.get(i);
            minDiff = Math.min(minDiff, diff);
        }
        return minDiff;
    }
}
 
 

---

🔍 Dry Run (for nums = [-2, 1, -3, 4, -1, 2, 1]):

Index	num	maxEndingHere	maxSoFar
0	-2	-2 → reset to 0	-2
1	1	1	1
2	-3	-2 → reset to 0	1
3	4	4	4
4	-1	3	4
5	2	5	5
6	1	6	6 ✅

Final result: 6

---

📈 Time & Space Complexity:

• Time: O(n)

• Space: O(1)

---

🔁 Follow-Up:

Try solving it using Divide and Conquer, which gives O(n log n) time complexity. It’s more complex but good for understanding recursive problem-solving.

---

Let me know if you want to include the divide and conquer version too!

---

💡 What is Kadane’s Algorithm?

Kadane’s Algorithm is used to find the maximum sum of a contiguous subarray in an array.
This problem is also known as the "Maximum Subarray Problem."

Example:

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output: 6 → (The subarray [4, -1, 2, 1] has the maximum sum 6)

🧠 Why Kadane’s Algorithm?

You could solve this using brute force by checking all possible subarrays and calculating their sums.
But that would take O(n²) time — very slow for large inputs.

Kadane’s Algorithm does it in O(n) time by cleverly keeping track of:

• Current sum of the subarray (maxEndingHere)

• Maximum sum seen so far (maxSoFar)

---

🔍 Step-by-step Explanation

Let’s say we have this array:

Index:         0   1   2   3   4   5   6
Array:        [-2, 1, -3, 4, -1, 2, 1]

Step 1: Initialization

• maxEndingHere = 0 → stores the sum ending at the current position

• maxSoFar = Integer.MIN_VALUE → tracks the highest sum so far

Step 2: Loop through each element:

For each element num in array:

maxEndingHere += num;
if (maxSoFar < maxEndingHere)
    maxSoFar = maxEndingHere;
if (maxEndingHere < 0)
    maxEndingHere = 0;

Step 3: How it works with the example:

i	num	maxEndingHere (sum so far)	maxSoFar (max sum)
0	-2	-2 → reset to 0	-2
1	1	1	1
2	-3	-2 → reset to 0	1
3	4	4	4
4	-1	3	4
5	2	5	5
6	1	6	6 ✅

So, max sum is 6.

---

📌 Final Code in Java

public class KadaneAlgorithm {
    public static int maxSubArray(int[] nums) {
        int maxSoFar = Integer.MIN_VALUE;
        int maxEndingHere = 0;
        for (int num : nums) {
            maxEndingHere += num;
            if (maxSoFar < maxEndingHere) {
                maxSoFar = maxEndingHere;
            }
            if (maxEndingHere < 0) {
                maxEndingHere = 0;
            }
        }
        return maxSoFar;
    }
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Maximum Subarray Sum: " + maxSubArray(nums));
    }
}

---

✅ When to Reset maxEndingHere?

If maxEndingHere becomes negative, we reset it to 0.
Why? Because a negative sum will only reduce the total sum of the next subarray.

---

⚡ Time and Space Complexity:

• Time Complexity: O(n) → only one pass

• Space Complexity: O(1) → no extra space needed

---