Maximum Subarray Sum problem and solutions in Java and Python

The Maximum Subarray Sum problem is a classic problem and the foundation of Kadane’s Algorithm. Let’s go step by step 👇

---

🧩 Problem Statement

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

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

---

⚙️ 1. Brute Force Approach (O(n²))

Check all possible subarrays and compute their sums.

✅ Java:

public int maxSubArrayBrute(int[] nums) {
    int maxSum = nums[0];
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            if (sum > maxSum) maxSum = sum;
        }
    }
    return maxSum;
}

✅ Python:

def max_subarray_brute(nums):
    max_sum = nums[0]
    n = len(nums)
    for i in range(n):
        curr_sum = 0
        for j in range(i, n):
            curr_sum += nums[j]
            max_sum = max(max_sum, curr_sum)
    return max_sum

🕒 Time: O(n²) 💾 Space: O(1)

---

⚡ 2. Optimized Approach — Kadane’s Algorithm (O(n))

🔍 Intuition:

• Keep a running sum currentSum of the subarray ending at current index.
• If currentSum < 0, reset it to 0 (start new subarray).
• Keep track of maximum sum seen so far.

---

✅ Java Solution:

public class MaxSubarray {
    public static int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int currentSum = 0;

        for (int num : nums) {
            currentSum += num;
            if (currentSum > maxSum) maxSum = currentSum;
            if (currentSum < 0) currentSum = 0;
        }
        return maxSum;
    }

    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)); // 6
    }
}

✅ Python Solution:

def max_subarray(nums):
    max_sum = nums[0]
    current_sum = 0

    for num in nums:
        current_sum += num
        max_sum = max(max_sum, current_sum)
        if current_sum < 0:
            current_sum = 0

    return max_sum

# Example
nums = [-2,1,-3,4,-1,2,1,-5,4]
print(max_subarray(nums))  # Output: 6

---

🧠 Dry Run Example

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Step-by-step:
currentSum = 0, maxSum = -2

1) -2 → currentSum=-2 → maxSum=-2 → reset currentSum=0
2) 1  → currentSum=1  → maxSum=1
3) -3 → currentSum=-2 → maxSum=1 → reset currentSum=0
4) 4  → currentSum=4  → maxSum=4
5) -1 → currentSum=3  → maxSum=4
6) 2  → currentSum=5  → maxSum=5
7) 1  → currentSum=6  → maxSum=6
8) -5 → currentSum=1  → maxSum=6
9) 4  → currentSum=5  → maxSum=6

✅ Maximum Subarray Sum = 6

---

🧭 Complexity

Approach	Time	Space
Brute Force	O(n²)	O(1)
Kadane’s	O(n)	O(1)

---

⚡ Variations of the Problem

1. Return the subarray itself, not just sum

   • Track start, end indices while running Kadane’s.

2. Circular Maximum Subarray

   • Subarray can wrap around end → use totalSum - minSubarray.

3. Maximum Product Subarray

   • Similar idea but handle negative numbers carefully.

4. K-Concatenation Maximum Sum

   • Array repeated k times → Kadane + prefix/suffix sums.

---