What is Max Crossing Subarray
The "max-crossing-subarray" problem is a classic algorithmic problem in computer science that involves finding the contiguous subarray with the largest sum, where the subarray crosses the midpoint of the given array.
In other words, given an array of numbers, the problem requires finding a contiguous subarray such that the sum of its elements is maximal among all contiguous subarrays that cross the midpoint of the original array.
The problem can be solved efficiently using the "divide and conquer" approach, where the array is recursively divided into two halves, and the maximum subarray crossing the midpoint is found by combining the maximum subarrays in the left and right halves. The time complexity of this algorithm is O(n log n), where n is the size of the input array.
Who invented it?
There is no single individual who can be credited with inventing this algorithm, as it is an example of a fundamental technique in algorithm design that has been developed and refined over many years by numerous researchers and practitioners in the field.
The "divide and conquer" approach, which is the basis for solving the "max-crossing-subarray" problem, has been used in various forms since ancient times, and is attributed to philosophers such as Aristotle and the ancient Indian mathematician Pingala.
In the context of computer science, the "divide and conquer" approach was popularized by the mathematician and computer scientist John von Neumann in the 1940s, and has since been applied to a wide range of problems, including the "max-crossing-subarray" problem.
The "divide and conquer" approach, which is the basis for solving the "max-crossing-subarray" problem, has been used in various forms since ancient times, and is attributed to philosophers such as Aristotle and the ancient Indian mathematician Pingala.
In the context of computer science, the "divide and conquer" approach was popularized by the mathematician and computer scientist John von Neumann in the 1940s, and has since been applied to a wide range of problems, including the "max-crossing-subarray" problem.
Pseudocode
// Find the maximum subarray that crosses the midpoint of the array
function max_crossing_subarray(array A, integer low, integer mid, integer high)
// Find the maximum subarray that ends at the midpoint
left_sum = -INF
sum = 0
for i = mid downto low
sum += A[i]
if sum > left_sum
left_sum = sum
max_left = i
// Find the maximum subarray that starts at the midpoint
right_sum = -INF
sum = 0
for j = mid + 1 to high
sum += A[j]
if sum > right_sum
right_sum = sum
max_right = j
// Combine the two subarrays to find the maximum subarray that crosses the midpoint
return (max_left, max_right, left_sum + right_sum)
// Find the maximum subarray of an array using the "divide and conquer" approach
function max_subarray(array A, integer low, integer high)
if low == high
return (low, high, A[low])
else
mid = floor((low + high) / 2)
// Find the maximum subarray in the left half
(left_low, left_high, left_sum) = max_subarray(A, low, mid)
// Find the maximum subarray in the right half
(right_low, right_high, right_sum) = max_subarray(A, mid + 1, high)
// Find the maximum subarray that crosses the midpoint
(cross_low, cross_high, cross_sum) = max_crossing_subarray(A, low, mid, high)
// Return the maximum of the three subarrays
if left_sum >= right_sum and left_sum >= cross_sum
return (left_low, left_high, left_sum)
else if right_sum >= left_sum and right_sum >= cross_sum
return (right_low, right_high, right_sum)
else
return (cross_low, cross_high, cross_sum)
In this pseudocode, A is the input array, low and high are the indices of the first and last elements of the subarray being considered, and mid is the index of the middle element.
The function max_crossing_subarray finds the maximum subarray that crosses the midpoint of the array, while the function max_subarray uses the "divide and conquer" approach to recursively find the maximum subarray of the entire array.
Note that in the pseudocode, INF represents infinity, and floor(x) represents the largest integer less than or equal to x.
The function max_crossing_subarray finds the maximum subarray that crosses the midpoint of the array, while the function max_subarray uses the "divide and conquer" approach to recursively find the maximum subarray of the entire array.
Note that in the pseudocode, INF represents infinity, and floor(x) represents the largest integer less than or equal to x.
Sample Code
// C++ code snippet
// Find the maximum subarray that crosses the midpoint of the array
tuple max_crossing_subarray(int A[], int low, int mid, int high) {
// Find the maximum subarray that ends at the midpoint
int left_sum = INT_MIN;
int sum = 0;
int max_left = 0;
for (int i = mid; i >= low; i--) {
sum += A[i];
if (sum > left_sum) {
left_sum = sum;
max_left = i;
}
}
// Find the maximum subarray that starts at the midpoint
int right_sum = INT_MIN;
sum = 0;
int max_right = 0;
for (int j = mid + 1; j <= high; j++) {
sum += A[j];
if (sum > right_sum) {
right_sum = sum;
max_right = j;
}
}
// Combine the two subarrays to find the maximum subarray that crosses the midpoint
return make_tuple(max_left, max_right, left_sum + right_sum);
}
// Find the maximum subarray of an array using the "divide and conquer" approach
tuple max_subarray(int A[], int low, int high) {
if (low == high) {
return make_tuple(low, high, A[low]);
} else {
int mid = (low + high) / 2;
// Find the maximum subarray in the left half
auto [left_low, left_high, left_sum] = max_subarray(A, low, mid);
// Find the maximum subarray in the right half
auto [right_low, right_high, right_sum] = max_subarray(A, mid + 1, high);
// Find the maximum subarray that crosses the midpoint
auto [cross_low, cross_high, cross_sum] = max_crossing_subarray(A, low, mid, high);
// Return the maximum of the three subarrays
if (left_sum >= right_sum && left_sum >= cross_sum) {
return make_tuple(left_low, left_high, left_sum);
} else if (right_sum >= left_sum && right_sum >= cross_sum) {
return make_tuple(right_low, right_high, right_sum);
} else {
return make_tuple(cross_low, cross_high, cross_sum);
}
}
}
int main() {
int A[] = {2, -1, 3, -4, 5, -2, 6, -7};
int n = sizeof(A) / sizeof(A[0]);
auto [low, high, sum] = max_subarray(A, 0, n - 1);
cout << "Maximum subarray: ";
for (int i = low; i <= high; i++) {
cout << A[i] << " ";
}
cout << "(sum = " << sum << ")" << endl;
return 0;
}
# Python code snippet
def max_crossing_subarray(A, low, mid, high):
# Find the maximum subarray that ends at the midpoint
left_sum = float('-inf')
sum = 0
for i in range(mid, low - 1, -1):
sum += A[i]
if sum > left_sum:
left_sum = sum
max_left = i
# Find the maximum subarray that starts at the midpoint
right_sum = float('-inf')
sum = 0
for j in range(mid + 1, high + 1):
sum += A[j]
if sum > right_sum:
right_sum = sum
max_right = j
# Combine the two subarrays to find the maximum subarray that crosses the midpoint
return (max_left, max_right, left_sum + right_sum)
def max_subarray(A, low, high):
if low == high:
return (low, high, A[low])
else:
mid = (low + high) // 2
# Find the maximum subarray in the left half
left_low, left_high, left_sum = max_subarray(A, low, mid)
# Find the maximum subarray in the right half
right_low, right_high, right_sum = max_subarray(A, mid + 1, high)
# Find the maximum subarray that crosses the midpoint
cross_low, cross_high, cross_sum = max_crossing_subarray(A, low, mid, high)
# Return the maximum of the three subarrays
if left_sum >= right_sum and left_sum >= cross_sum:
return (left_low, left_high, left_sum)
elif right_sum >= left_sum and right_sum >= cross_sum:
return (right_low, right_high, right_sum)
else:
return (cross_low, cross_high, cross_sum)
A = [2, -1, 3, -4, 5, -2, 6, -7]
low, high, sum = max_subarray(A, 0, len(A) - 1)
print("Maximum subarray:", A[low:high+1], "(sum =", sum, ")")
public class MaxSubarray {
public static int[] maxCrossingSubarray(int[] A, int low, int mid, int high) {
// Find the maximum subarray that ends at the midpoint
int leftSum = Integer.MIN_VALUE;
int sum = 0;
int maxLeft = 0;
for (int i = mid; i >= low; i--) {
sum += A[i];
if (sum > leftSum) {
leftSum = sum;
maxLeft = i;
}
}
// Find the maximum subarray that starts at the midpoint
int rightSum = Integer.MIN_VALUE;
sum = 0;
int maxRight = 0;
for (int j = mid + 1; j <= high; j++) {
sum += A[j];
if (sum > rightSum) {
rightSum = sum;
maxRight = j;
}
}
// Combine the two subarrays to find the maximum subarray that crosses the midpoint
return new int[]{maxLeft, maxRight, leftSum + rightSum};
}
public static int[] maxSubarray(int[] A, int low, int high) {
if (low == high) {
return new int[]{low, high, A[low]};
} else {
int mid = (low + high) / 2;
// Find the maximum subarray in the left half
int[] leftSubarray = maxSubarray(A, low, mid);
int leftLow = leftSubarray[0];
int leftHigh = leftSubarray[1];
int leftSum = leftSubarray[2];
// Find the maximum subarray in the right half
int[] rightSubarray = maxSubarray(A, mid + 1, high);
int rightLow = rightSubarray[0];
int rightHigh = rightSubarray[1];
int rightSum = rightSubarray[2];
// Find the maximum subarray that crosses the midpoint
int[] crossSubarray = maxCrossingSubarray(A, low, mid, high);
int crossLow = crossSubarray[0];
int crossHigh = crossSubarray[1];
int crossSum = crossSubarray[2];
// Return the maximum of the three subarrays
if (leftSum >= rightSum && leftSum >= crossSum) {
return new int[]{leftLow, leftHigh, leftSum};
} else if (rightSum >= leftSum && rightSum >= crossSum) {
return new int[]{rightLow, rightHigh, rightSum};
} else {
return new int[]{crossLow, crossHigh, crossSum};
}
}
}
public static void main(String[] args) {
int[] A = {2, -1, 3, -4, 5, -2, 6, -7};
int[] subarray = maxSubarray(A, 0, A.length - 1);
int low = subarray[0];
int high = subarray[1];
int sum = subarray[2];
System.out.print("Maximum subarray: [");
for (int i = low; i <= high; i++) {
System.out.print(A[i]);
if (i < high) {
System.out.print(", ");
}
}
System.out.println("] (sum = " + sum + ")");
}
Time and Space Complexity
- The time complexity of the "max-crossing-subarray" problem using the "divide and conquer" approach is O(n log n), where n is the length of the input array. This is because the problem is divided into two subproblems of roughly half the size at each recursive call, and then the solutions to those subproblems are combined in O(n) time.
The space complexity of the algorithm is O(log n), which is the maximum depth of the recursive call stack. This is because the algorithm uses a recursive approach and creates new subarrays on each recursive call, so the maximum number of subarrays that can exist at one time is equal to the depth of the call stack, which is O(log n).
Advantages
- The "divide and conquer" approach is a widely used algorithmic technique for solving various problems efficiently.
- The "max-crossing-subarray" algorithm has a relatively good time complexity of O(n log n), which is faster than some other algorithms for finding the maximum subarray, such as the brute force approach that has a time complexity of O(n^2).
- The algorithm is easy to implement and understand, making it a good choice for beginners in algorithm design and analysis.
Disadvantages
- The "max-crossing-subarray" algorithm requires more space than some other algorithms because it creates new subarrays on each recursive call. This can lead to higher memory usage, especially for large input arrays.
- Although the algorithm has a good time complexity of O(n log n), it is not as fast as some specialized algorithms for solving specific types of subarray problems, such as dynamic programming approaches for finding the maximum subarray sum in a sliding window.
- The algorithm has a relatively high constant factor due to the recursive calls and the additional overhead of combining the subarrays, making it slower than some other algorithms for small input sizes.