Difficulty: Medium, Asked-in: Facebook, Microsoft, Amazon, Morgan Stanley, Walmart.
Key takeaways
Given an array X[] of n integers, write a program to find the maximum sum of a subarray among all subarrays. A subarray is a contiguous segment of elements from X[i] to X[j], where 0 <= i <= j <= n - 1.
Input: X[] = [-4, 5, 7, -6, 10, -15, 3], Output: 16
Explanation: The subarray [5, 7, -6, 10] has the maximum sum.
Input: X[] = [-3, 1, -2, 6, -4, 2], Output: 6
Explanation: Here single element subarray [6] has the maximum sum.
Input: X[] = [5, 7, 6, 10, 3], Output: 31
Explanation: All array elements are non-negative. So the maximum subarray sum would be the sum of the entire array.
The most basic solution is to explore all possible subarrays (for all i and j, where i ≤ j), calculate the sum of each subarray and track the maximum among them.
At the end of the nested loop, we return maxSubarraySum.
int findMaxSubarraySum(int X[], int n)
{
int maxSubarraySum = INT_MIN
for (int i = 0; i < n; i = i + 1)
{
for (int j = i; j < n; j = j + 1)
{
int subarraySum = 0
for (int k = i; k <= j; k = k + 1)
subarraySum = subarraySum + X[k]
if (subarraySum > maxSubarraySum)
maxSubarraySum = subarraySum
}
}
return maxSubarraySum
}
We are using three nested loops i.e. exploring each subarray using two outer loops and calculating their sum using the innermost loop. So time complexity = O(n^3). We are using constant extra space, so space complexity = O(1).
Now, the critical questions are: Can we optimize the above approach further? Is it necessary to run the innermost loop from k = i to j? If we observe closely, we can easily calculate the subarray sum from i to j + 1 in O(1), if we know the sub-array sum from i to j. The formula is: Subarray sum from i to j + 1 = Subarray sum from i to j + X[j + 1].
So instead of using three nested loops, we can use only two nested loops: the outer loop to pick the starting index, and the inner loop to calculate the sum of all sub-arrays starting from that index. Here, there is a no need to run the innermost loop to calculate the sum of each subarray.
int findMaxSubarraySum(int X[], int n)
{
int maxSubarraySum = INT_MIN
for (int i = 0; i < n; i = i + 1)
{
int subarraySum = 0
for (int j = i; j < n; j = j + 1)
{
subarraySum = subarraySum + X[j]
if (subarraySum > maxSubarraySum)
maxSubarraySum = subarraySum
}
}
return maxSubarraySum
}
We are using two nested loops to explore each subarray and performing O(1) operation at each iteration. Total count of loop iterations = Total count of different subarrays = n + n - 1 + n - 2 + ... + 2 + 1 = n(n + 1)/2 = O(n²). So time complexity = Total count of loop iterations * O(1) = O(n²). We are using constant extra space, so space complexity = O(1).
Now critical questions are: Can we improve time complexity further? Can we solve this problem using recursion or dividing the problem into smaller subproblems? Let's think!
Suppose we want to calculate the maximum sub-array sum of the array X[l, r], where l and r are the left and right ends. Now we divide the array into two equal subarrays by calculating the mid: X[l, mid] and X[mid + 1, r]. If we observe, the subarray with the maximum sum must lie in one of the following places:
We can recursively find the maximum sub-array sum of X[l, mid] and X[mid + 1, r] because these two are smaller instances of the problem of finding the maximum sub-array sum.
int leftMaxSum = findMaxSubarraySum (X, l, mid)
int rightMaxSum = findMaxSubarraySum (X, mid + 1, r)
Now we need to calculate the maximum sub-array that crosses the mid-point and take the maximum of all three possibilities to get overall max subarray sum.
int crossingMaxSum = maxCrossingSum(X, l, mid, r)
return max(leftMaxSum, rightMaxSum, crossingMaxSum)
Base case: When l == r, there is only one element in the array, and we can directly return the maximum subarray sum as X[l] or X[r]. This is the smallest version of the problem, where the recursion will return the value directly.
int getMaxSubarraySum (int X[], int l, int r)
{
if (l == r)
return X[l]
else
{
int mid = l + (r - l)/2
int leftMaxSum = getMaxSubarraySum (X, l, mid)
int rightMaxSum = getMaxSubarraySum (X, mid + 1, r)
int crossingMaxSum = maxCrossingSum (X, l, mid, r)
return max (leftMaxSum, rightMaxSum, crossingMaxSum)
}
}
Suppose X[i, j] is the subarray with the maximum sum crossing the midpoint. So we can break this subarray into two parts: 1) Subarray X[i, mid] with the maximum sum in the left part, 2) Subarray X[mid + 1, j] with the maximum sum in the right part. So, to get the overall maximum sum crossing the midpoint, we find these two sums by separately traversing the left and right parts and adding their values. Here are the steps:
Step 1: We find the maximum contiguous sum of the left half, X[i, mid].
int sum = 0
int maxLeftSum = INT_MIN
for(int i = mid; i <= l; i = i - 1)
{
sum = sum + X[i]
if (sum > maxLeftSum)
maxLeftSum = sum
}
Step 2: Now we find the maximum contiguous sum of the right half, X[mid + 1, j].
sum = 0
int maxRightSum = INT_MIN
for(int i = mid + 1; i <= r; i = i + 1)
{
sum = sum + X[i]
if (sum > maxRightSum)
maxRightSum = sum
}
Step 3: Finally, to get the maximum contiguous subarray sum crossing the mid, we return the sum of variables maxLeftSum and maxRightSum.
Pseudocode to find max subarray sum crossing
int maxCrossingSum(int X[], int l, int mid, int r)
{
int sum = 0
int maxLeftSum = INT_MIN
for (int i = mid; i >= l; i = i - 1)
{
sum = sum + X[i]
if (sum > maxLeftSum)
maxLeftSum = sum
}
sum = 0
int maxRightSum = INT_MIN
for (int i = mid + 1; i <= r; i = i + 1)
{
sum = sum + X[i]
if (sum > maxRightSum)
maxRightSum = sum
}
return (maxLeftSum + maxRightSum)
}
Suppose T(n) is the time complexity of finding the maximum subarray sum using divide and conquer approach. To calculate the overall time complexity, we need to add the time complexities of the divide, conquer, and combine steps.
Final recurrence relation
This recurrence is the same as a recurrence relation of the merge sort. So overall time complexity = O(nlogn). For a better understanding of this analysis, you can explore analysis of recursion blog.
Space complexity is equal to the size of the recursion call stack, which depends on the height of the recursion tree. At each stage, the input size decreases by 2, so the height of the recursion tree will be O(logn). Space complexity = O(logn). Think!
If we observe, the subarray with maximum sum must be ending at some index in the array. So one idea would be to find the maximum subarray sum ending at all indexes and store their values in an extra memory. Now we can get the max subarray sum of the whole array by finding the maximum of the values stored in the extra memory. The critical question is: How can we implement this? Let's think!
Suppose we take an array maxSumEnding[] of size n, where maxSumEnding[i] is the maximum subarray sum ending at index i. Now how can we fill values in this array? Here is an insight: If we know the max subarray sum ending at i - 1 index, we can easily calculate the max subarray sum ending at index i.
Finally, to get the maximum subarray sum of the whole array, we return the maximum value stored in the array maxSumEnding[]. This problem falls under the dynamic programming category because we are storing the solution of sub-problems and solving the larger problem using the solution of smaller sub-problems.
Now we traverse the array from i = 1 to n - 1. At ith iteration, we calculate the max subarray sum ending at index i and store it at maxSumEnding[i].
int findMaxSubarraySum(int X[], int n)
{
int maxSumEnding[n]
maxSumEnding[0] = X[0]
for (int i = 1; i < n; i = i + 1)
{
if (maxSumEnding[i - 1] > 0)
maxSumEnding[i] = X[i] + maxSumEnding[i - 1]
else
maxSumEnding[i] = X[i]
}
int maxSubarraySum = INT_MIN
for (int i = 0; i < n; i = i + 1)
maxSubarraySum = max(maxSubarraySum, maxSumEnding[i])
return maxSubarraySum
}
Here is another implementation: Instead of calculating the max of the maxSumEnding[] in a separate loop, we can track the maximum on the go in the same loop where we are updating maxSumEnding[].
int findMaxSubarraySum(int X[], int n)
{
int maxSumEnding[n]
maxSumEnding[0] = X[0]
int maxSubarraySum = X[0]
for (int i = 1; i < n; i = i + 1)
{
// Calculate maxSumEnding for the current position
if (maxSumEnding[i-1] > 0)
maxSumEnding[i] = X[i] + maxSumEnding[i-1]
else
maxSumEnding[i] = X[i]
// Track the maximum subarray sum encountered so far
maxSubarraySum = max(maxSubarraySum, maxSumEnding[i])
}
return maxSubarraySum
}
We are traversing the array and performing O(1) operation at each iteration. Time complexity = O(n). Space complexity = O(n), for extra array maxSumEnd[n].
Now, can we solve this problem in O(1) space? Can we solve this problem in a single traversal? Here is the thought process for optimizing the solution using Kadane's algorithm.
If we observe the filling pattern of array maxSumEnding[n] in the previous approach, we only need one previous value at i - 1 index to calculate the maximum subarray sum ending at index i. So instead of using an extra array of size n, we can track the max subarray sum ending at the current index i using some variable maxSumEndingHere.
So in this approach, we can use a single loop and two extra variables. This means there is no need for O(n) space. This is the Kadane's algorithm idea! We can use similar ideas to solve various questions.
Now we run a loop from i = 1 to n - 1. At each ith iteration:
int findMaxSubarraySum(int X[], int n)
{
int maxSumSoFar = X[0]
int maxSumEndingHere = X[0]
for (int i = 1; i < n; i = i + 1)
{
maxSumEndingHere = max(maxSumEndingHere + X[i], X[i])
if (maxSumSoFar < maxSumEndingHere)
maxSumSoFar = maxSumEndingHere
}
return maxSumSoFar
}
We are traversing each element using a single loop and performing a constant operation. So time complexity = O(n). Since we are using a constant number of variables, space complexity = O(1).
If you have any queries or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy coding, Enjoy algorithms!