Maximum SubArray

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.

Approach 1: Brute Force

Explanation: Generate all possible subarrays and calculate their sum to find the maximum.

Time Complexity: O(n3)

Space Complexity: O(1)

function maxSubArray(arr):
    n = length(arr)
    maxSum = -infinity
    
    for i = 0 to n-1:
        for j = i to n-1:
            currentSum = 0
            for k = i to j:
                currentSum = currentSum + arr[k]
            maxSum = max(maxSum, currentSum)
    
    return maxSum

Approach 2: Divide and Conquer

Explanation: Divide the array into two halves. The maximum subarray can be in the left half, right half, or crossing the middle. Recursively find the maximum in each case.

Time Complexity: O(n log n)

Space Complexity: O(log n) due to recursive stack 

function maxCrossingSum(arr, low, mid, high):
    leftSum = -infinity
    sum = 0
    for i = mid down to low:
        sum = sum + arr[i]
        leftSum = max(leftSum, sum)
    
    rightSum = -infinity
    sum = 0
    for i = mid+1 to high:
        sum = sum + arr[i]
        rightSum = max(rightSum, sum)
    
    return leftSum + rightSum

function maxSubArrayDC(arr, low, high):
    if low == high:
        return arr[low]
    
    mid = (low + high) / 2
    
    leftMax = maxSubArrayDC(arr, low, mid)
    rightMax = maxSubArrayDC(arr, mid+1, high)
    crossMax = maxCrossingSum(arr, low, mid, high)
    
    return max(leftMax, rightMax, crossMax)

function maxSubArray(arr):
    return maxSubArrayDC(arr, 0, length(arr)-1)

Approach 3: Kadane's Algorithm (Dynamic Programming)

Explanation: Keep track of the maximum sum ending at each position. At each element, decide whether to extend the existing subarray or start a new one.

Time Complexity: O(n)

Space Complexity: O(1)

function maxSubArray(arr):
    n = length(arr)
    maxSum = arr[0]
    currentSum = arr[0]
    
    for i = 1 to n-1:
        currentSum = max(arr[i], currentSum + arr[i])
        maxSum = max(maxSum, currentSum)
    
    return maxSum

Though Divide and Conquer is not the most optimal approach for this problem, it is included here to illustrate the Divide and Conquer pattern. The optimal solution is Kadane's Algorithm with O(n) time complexity.


Flowchart