Maximum Subarray Problem
Maximum Subarray Problem
The maximum subarray problem is the task of finding the largest possible sum of a contiguous subarray, within a given one-dimensional array A[1…n] of numbers.
For a given array, the goal is to identify a starting and ending index such that the sum of all elements between these two indices (inclusive) is greater than the sum of any other contiguous subarray.
Consider the array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
The maximum subarray is [4, -1, 2, 1], and its sum is 4+(−1)+2+1=6. No other contiguous subarray in the given array has a sum greater than 6.
Brute-Force Approaches
A simple but inefficient solution is to check every possible contiguous subarray. This involves using two nested loops to define the start and end points of the subarray.
This can be optimized to O(n^2) by calculating the sum of the subarray in the inner loop instead of using a third loop.
O(n^2) Time and O(1) Space
public class MaximumSubarrayBruteForce2 {
public static void main(String[] args) {
int[] A = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
int maxSum = 0;
int beginIndex = 0;
int endIndex = 1;
for (int i = 0; i < A.length; i++) {
int tempSum = 0;
for (int j = i; j < A.length; j++) {
tempSum = tempSum + A[j];
if (tempSum > maxSum) {
maxSum = tempSum;
beginIndex = i;
endIndex = j;
}
}
}
System.out.println("beginIndex:" + beginIndex + " endIndex:" + endIndex);
System.out.println("between " + A[beginIndex] + " and " + A[endIndex]);
}
}
Using a third inner loop
Another brute force approach uses a third loop to calculate the sum. The time complexity of this approach is O(n^3), where ’n’ is the number of elements in the array. But this is much worse compared to using two loops.
public class MaximumSubarrayBruteForce1 {
public static void main(String[] args) {
int[] A = new int[] {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int maxSum = 0;
int beginIndex = 0;
int endIndex = 1;
for (int i = 0; i < A.length; i++) {
for (int j = i; j < A.length; j++) {
int tempSum = 0;
for (int k = i; k <= j; k++) {
tempSum = tempSum + A[k];
if (tempSum > maxSum) {
maxSum = tempSum;
beginIndex = i;
endIndex = j;
}
}
}
}
System.out.println("beginIndex:" + beginIndex + " endIndex:" + endIndex);
System.out.println("between " + A[beginIndex] + " and " + A[endIndex]);
}
}
Divide and Conquer
O(n*logn) time and O(n) space
For this specific challenge, we recursively divide a longer sequence into two halves until there is only one integer in each subsequence. To merge two subsequences, say subsequence A and B, we compare the maximum subsequence sum of A and B with the maximum sum of subsequence that bridges A and B.
Since the subsequence needs to be contiguous, the bridging subsequence surely includes the right most element of subsequence A and left most element of subsequence B. Therefore, we can extend from these two points toward the ends to find the maximum sum bridging subsequence that includes these two points.
Divide the given array in two halves and return the maximum of following three:
- Maximum subarray sum in left half.
- Maximum subarray in left and right half can be found easily by two recursive calls.
- Maximum subarray sum in right half.
- Maximum subarray in left and right half can be found easily by two recursive calls.
- Maximum subarray sum such that the subarray crosses the midpoint.
- To find maximum subarray sum such that the subarray crosses the midpoint, find the maximum sum starting from mid point and ending at some point on left of mid, then find the maximum sum starting from mid + 1 and ending with some point on right of mid + 1.
- Finally, combine the two and return the maximum among left, right and combination of both.
https://www.geeksforgeeks.org/dsa/maximum-subarray-sum-using-divide-and-conquer-algorithm/
Dynamic Programming
O(n) Time and O(1) Space
Kadane’s algorithm
Dynamic Programming is to synthesize the solution for big problems with the solutions of smaller problems. The core idea underlying Dynamic Programming is to develop a recursion function to transfer from one state to another. Suppose we have known the maximum subsequence sum for the first i elements (A(1)…A(i)). For sequence A(1)…A(i + 1), we need to determine whether the maximum subsequence includes element A(i + 1) or not. If it is, the maximum subsequence for the first i + 1 elements is a subsequence ended with element A(i). Otherwise, the maximum subsequence for the first i + 1 elements is the same as that of the first i elements. The recursion function is defined as follows:
M (i) = max{M (i − 1), tempSum(i)}
where tempSum(i) is the maximum subsequence sum ended with element A(i).
https://www.geeksforgeeks.org/dsa/largest-sum-contiguous-subarray/
Extended to 2-D arrays or Matrices
https://www.geeksforgeeks.org/dsa/maximum-sum-submatrix/
Applications
The maximum subarray problem serves as an excellent introductory problem for algorithm design and analysis. It has applications in various fields, including:
- Financial analysis: Identifying periods of maximum profit in a stock’s price history.
- Bioinformatics: Analyzing sequences to find regions with the highest density of a certain characteristic.
- Image processing: Finding the brightest region in a digital image.
Financial Analysis: In finance, especially in stock market analysis, the Maximum Subarray problem can be used to determine the most profitable period to invest in stocks. This is analogous to finding a period where the net change of stock prices is maximized. Data Analysis: It’s also applicable in data analysis for detecting significant periods in datasets, like finding a time frame with the highest activity or concentration of events in sensor data or network traffic. Image Processing: In computer vision and image processing, variations of this problem help in detecting areas of images with maximum intensity or specific features, which is crucial in tasks like object detection and recognition.