Question 37 : Largest sum contiguous subarray.

Largest sum contiguous subarray is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum.

For example :

for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; 
the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6

Input:  [−2,1,−3,4,−1,2,1,−5,4]
Output: 6
Explanation: [4, −1, 2, 1] → sum = 6

   maxSum(i) = Max of (maxSum(i-1) + a[i] , a[i])

Kadane’s Algorithm (Optimal)

Scan the array while maintaining:

• currentSum — best sum ending at current index
• maxSum — best sum seen so far

At each element:

• currentSum = max(num, currentSum + num)
• maxSum = max(maxSum, currentSum)

public class MaxSubarray {

    public static int maxSubArray(int[] arr) {
        int currentSum = arr[0];
        int maxSum     = arr[0];

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

        return maxSum;
    }
}

Python

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

    for num in arr[1:]:
        current_sum = max(num, current_sum + num)
        max_sum     = max(max_sum, current_sum)

    return max_sum

Prefix Sum + Min Prefix

Prefix sum means:

prefix[i] = sum of elements from index 0 to i

Example:

For:

[-2, 1, -3, 4]

Prefix array becomes:

i=0 → -2
i=1 → -2+1 = -1
i=2 → -1-3 = -4
i=3 → -4+4 = 0

So:

prefix = [-2, -1, -4, 0]

Key Idea

• Any subarray sum can be written as:
• subarray(i → j) = prefix[j] - prefix[i-1]
• So if we want the biggest subarray ending at j:
• We want:
• prefix[j] - (smallest prefix before j)

Why Smallest Prefix?

• Because:
• currentSubarray = currentPrefix - somePreviousPrefix

public class MaxSubarrayPrefix {

    public static int maxSubArray(int[] arr) {
        int minPrefix = 0;
        int prefix    = 0;
        int maxSum    = Integer.MIN_VALUE;

        for (int num : arr) {
            prefix += num;
            maxSum = Math.max(maxSum, prefix - minPrefix);
            minPrefix = Math.min(minPrefix, prefix);
        }

        return maxSum;
    }
}

Python 
def max_subarray_prefix(arr):
    min_prefix = 0
    prefix     = 0
    max_sum    = float("-inf")

    for num in arr:
        prefix += num
        max_sum = max(max_sum, prefix - min_prefix)
        min_prefix = min(min_prefix, prefix)

    return max_sum

 Brute Force (All Subarrays)
public class MaxSubarrayBrute {

    public static int maxSubArray(int[] arr) {
        int maxSum = Integer.MIN_VALUE;

        for (int i = 0; i < arr.length; i++) {
            int sum = 0;
            for (int j = i; j < arr.length; j++) {
                sum += arr[j];
                maxSum = Math.max(maxSum, sum);
            }
        }
        return maxSum;
    }
}

Python 
def max_subarray_brute(arr):
    max_sum = float("-inf")
    for i in range(len(arr)):
        sum_ = 0
        for j in range(i, len(arr)):
            sum_ += arr[j]
            max_sum = max(max_sum, sum_)
    return max_sum



  
    
    
    
    
  

  

    
Approach
    
Time Complexity
    
Space Complexity
    
Best Use
  

  

    

      Kadane’s algorithm
    
    

      O(n)
    
    

      O(1)
    
    

      ⭐ Best & optimal
    
  

  

    

      Prefix sum + min prefix
    
    

      O(n)
    
    

      O(1)
    
    

      ✔ Same complexity
    
  

  

    

      Brute force nested
    
    

      O(n²)
    
    
O(1)
    

      ❌ Slow