Maximum Subarray Sum
Solve the Maximum Subarray Sum problem: Given an integer array, find the contiguous subarray that has the largest sum. For example, for the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the maximum subarray sum is [4, -1, 2, 1], which sums to 6.
Solution Steps
When we need to find the maximum subarray sum in an array, we can use a divide-and-conquer algorithm. The basic idea of this algorithm is to recursively divide the array into smaller subarrays and then solve for the maximum subarray sum in both the left and right subarrays separately. Finally, we must also consider the maximum subarray sum that crosses the midpoint.
The specific steps are as follows:
- First, we divide the given array into two smaller subarrays, namely the left subarray and the right subarray. The division method involves finding the middle position of the array.
- Then, we recursively solve for the maximum subarray sum in both the left and right subarrays. This step can be achieved by calling the divide-and-conquer algorithm again. The recursive termination condition is when the subarray contains only one element, at which point we directly return that element.
- Next, we need to consider the maximum subarray sum that crosses the midpoint. We extend from the midpoint to the left to find the maximum subarray sum on the left side, and then extend from the midpoint to the right to find the maximum subarray sum on the right side. This step is implemented using linear time operations.
- Finally, we compare the maximum subarray sum of the left subarray, the maximum subarray sum of the right subarray, and the maximum subarray sum that crosses the midpoint, taking the largest value as the final maximum subarray sum.
By recursively dividing and merging subarrays, we can find the maximum subarray sum for the entire array. The key to this divide-and-conquer algorithm lies in breaking down the problem into smaller subproblems and considering cases where the optimal solution may cross the boundary of the subarrays during the merge process. This significantly reduces the problem size and improves the efficiency of the algorithm.
Solution
::: code-tabs
@tab Java
public class MaximumSubarraySum {
public static int findMaxSubarray(int[] arr) {
return findMaxSubarray(arr, 0, arr.length - 1);
}
private static int findMaxSubarray(int[] arr, int low, int high) {
if (low == high) {
return arr[low];
}
int mid = (low + high) / 2;
int leftMaxSum = findMaxSubarray(arr, low, mid);
int rightMaxSum = findMaxSubarray(arr, mid + 1, high);
int crossMaxSum = findMaxCrossingSubarray(arr, low, mid, high);
return Math.max(Math.max(leftMaxSum, rightMaxSum), crossMaxSum);
}
private static int findMaxCrossingSubarray(int[] arr, int low, int mid, int high) {
int leftSum = Integer.MIN_VALUE;
int sum = 0;
for (int i = mid; i >= low; i--) {
sum += arr[i];
leftSum = Math.max(leftSum, sum);
}
int rightSum = Integer.MIN_VALUE;
sum = 0;
for (int i = mid + 1; i <= high; i++) {
sum += arr[i];
rightSum = Math.max(rightSum, sum);
}
return leftSum + rightSum;
}
public static void main(String[] args) {
int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int maxSum = findMaxSubarray(arr);
System.out.println("Maximum Subarray Sum: " + maxSum);
}
}
@tab JavaScript
function findMaxSubarray(arr) {
return findMaxSubarrayHelper(arr, 0, arr.length - 1);
}
function findMaxSubarrayHelper(arr, low, high) {
if (low === high) {
return arr[low];
}
const mid = Math.floor((low + high) / 2);
const leftMaxSum = findMaxSubarrayHelper(arr, low, mid);
const rightMaxSum = findMaxSubarrayHelper(arr, mid + 1, high);
const crossMaxSum = findMaxCrossingSubarray(arr, low, mid, high);
return Math.max(leftMaxSum, rightMaxSum, crossMaxSum);
}
function findMaxCrossingSubarray(arr, low, mid, high) {
let leftSum = Number.NEGATIVE_INFINITY;
let sum = 0;
for (let i = mid; i >= low; i--) {
sum += arr[i];
leftSum = Math.max(leftSum, sum);
}
let rightSum = Number.NEGATIVE_INFINITY;
sum = 0;
for (let i = mid + 1; i <= high; i++) {
sum += arr[i];
rightSum = Math.max(rightSum, sum);
}
return leftSum + rightSum;
}
const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
const maxSum = findMaxSubarray(arr);
console.log("Maximum Subarray Sum:", maxSum);
@tab Python
def find_max_subarray(arr):
return find_max_subarray_helper(arr, 0, len(arr) - 1)
def find_max_subarray_helper(arr, low, high):
if low == high:
return arr[low]
mid = (low + high) // 2
left_max_sum = find_max_subarray_helper(arr, low, mid)
right_max_sum = find_max_subarray_helper(arr, mid + 1, high)
cross_max_sum = find_max_crossing_subarray(arr, low, mid, high)
return max(left_max_sum, right_max_sum, cross_max_sum)
def find_max_crossing_subarray(arr, low, mid, high):
left_sum = float('-inf')
sum = 0
for i in range(mid, low - 1, -1):
sum += arr[i]
left_sum = max(left_sum, sum)
right_sum = float('-inf')
sum = 0
for i in range(mid + 1, high + 1):
sum += arr[i]
right_sum = max(right_sum, sum)
return left_sum + right_sum
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum = find_max_subarray(arr)
print("Maximum Subarray Sum:", max_sum)
@tab Go
package main
import "fmt"
func findMaxSubarray(arr []int) int {
return findMaxSubarrayHelper(arr, 0, len(arr)-1)
}
func findMaxSubarrayHelper(arr []int, low, high int) int {
if low == high {
return arr[low]
}
mid := (low + high) / 2
leftMaxSum := findMaxSubarrayHelper(arr, low, mid)
rightMaxSum := findMaxSubarrayHelper(arr, mid+1, high)
crossMaxSum := findMaxCrossingSubarray(arr, low, mid, high)
return max(leftMaxSum, rightMaxSum, crossMaxSum)
}
func findMaxCrossingSubarray(arr []int, low, mid, high int) int {
leftSum := -1 << 31
sum := 0
for i := mid; i >= low; i-- {
sum += arr[i]
leftSum = max(leftSum, sum)
}
rightSum := -1 << 31
sum = 0
for i := mid + 1; i <= high; i++ {
sum += arr[i]
rightSum = max(rightSum, sum)
}
return leftSum + rightSum
}
func max(a, b, c int) int {
if a >= b && a >= c {
return a
} else if b >= a && b >= c {
return b
} else {
return c
}
}
func main() {
arr := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
maxSum := findMaxSubarray(arr)
fmt.Println("Maximum Subarray Sum:", maxSum)
}
:::