Largest Sum Contiguous Subarray [V.V.V.V IMP]

Problem Statement

Given an array of integers (can contain negative numbers), find the contiguous subarray with the largest sum.

Example:

• Input: arr = [-2, -3, 4, -1, -2, 1, 5, -3]
• Output: 7 (The subarray [4, -1, -2, 1, 5] has the largest sum = 7)

Noob-Friendly Explanation

Imagine you're walking along a number line and at each step you collect points (positive or negative). You want to find the best stretch of consecutive steps that gives you the most points. You get to choose where to start and where to stop. If you pick a stretch with too many negative numbers, your total drops. The trick is finding the sweet spot — the stretch that maximizes your total.

This is one of the most famous problems in computer science, known as Kadane's Algorithm. It shows up everywhere in interviews!

Approach 1: Brute Force

Intuition

Check every possible subarray by trying all start and end points. Calculate the sum of each subarray and track the maximum.

Algorithm

1. For each starting index i, iterate through all ending indices j.
2. Calculate the sum of the subarray from i to j.
3. Track the maximum sum found.

class Solution {
    public static int maxSubArrayBrute(int[] arr) {
        int n = arr.length;
        int maxSum = Integer.MIN_VALUE;

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

        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {-2, -3, 4, -1, -2, 1, 5, -3};
        System.out.println(maxSubArrayBrute(arr)); // Output: 7
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - two nested loops
• Space Complexity: O(1) - only a few variables

Approach 2: Optimal (Kadane's Algorithm)

Intuition

The key insight is: at each position, we either extend the previous subarray or start a new one. If the running sum becomes negative, it's better to start fresh from the next element because a negative sum would only drag down any future subarray.

Algorithm

1. Initialize currentMax = arr[0] and globalMax = arr[0].
2. For each element from index 1 onwards:
   • currentMax = max(arr[i], currentMax + arr[i]) — either start new or extend.
   • globalMax = max(globalMax, currentMax) — update the best answer.
3. Return globalMax.

class Solution {
    public static int maxSubArray(int[] arr) {
        int currentMax = arr[0];
        int globalMax = arr[0];

        for (int i = 1; i < arr.length; i++) {
            // Either extend the previous subarray or start fresh
            currentMax = Math.max(arr[i], currentMax + arr[i]);
            // Update global maximum
            globalMax = Math.max(globalMax, currentMax);
        }

        return globalMax;
    }

    public static void main(String[] args) {
        int[] arr = {-2, -3, 4, -1, -2, 1, 5, -3};
        System.out.println(maxSubArray(arr)); // Output: 7
    }
}

Complexity Analysis

• Time Complexity: O(n) - single pass through the array
• Space Complexity: O(1) - only two variables used