Difficulty: Medium, Asked-in: Facebook, Microsoft, Amazon, Morgan Stanley, Walmart, Flipkart, Hike, Zoho.
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 of array X[] 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, 2, -1, 4, -2], Output: 5
Explanation: The subarray [2, -1, 4] 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 return 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;
}
def findMaxSubarraySum(X, n):
maxSubarraySum = -maxsize
for i in range(n):
for j in range(i, n):
subarraySum = 0
for k in range(i, j + 1):
subarraySum = subarraySum + X[k]
if subarraySum > maxSubarraySum:
maxSubarraySum = subarraySum
return maxSubarraySum
We are using three nested loops: Exploring each subarray using two outer loops and calculating their sum using the innermost loop. So time complexity = O(n^3). Note: You can explore analysis of loop blog for understanding the exact analysis of this loop.
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? Let's think!
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. Here is the formula: Subarray sum from i to j + 1 = Subarray sum from i to j + X[j + 1].
This is the optimized version of the above approach. Here we can use only two nested loops: the outer loop to pick the starting index, and the inner loop to calculate the running sum of all sub-arrays starting from that index. So we can easily avoid the innermost loop to calculate the sum of each subarray every time.
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;
}
def findMaxSubarraySum(X, n):
maxSubarraySum = -maxsize
for i in range(n):
subarraySum = 0
for j in range(i, n):
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 smaller sub-problems or the divide and conquer approach? 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-index: X[l, mid] and X[mid + 1, r]. If we observe, the sub-array X[i, j] 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)
}
}
The maximum subarray sum crossing the midpoint will include two subarrays: Subarray X[i, mid] with the maximum sum in the left part and subarray X[mid + 1, j] with the maximum sum in the right part. So, to get the overall maximum sum crossing the midpoint, we need to 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[l, 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, r].
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.
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);
}
int findMaxSubarraySum(int X[], int l, int r)
{
if (l == r)
return X[l];
else
{
int mid = l + (r - l) / 2;
int leftMaxSum = findMaxSubarraySum(X, l, mid);
int rightMaxSum = findMaxSubarraySum(X, mid + 1, r);
int crossingMaxSum = maxCrossingSum(X, l, mid, r);
return max({leftMaxSum, rightMaxSum, crossingMaxSum});
}
}
def maxCrossingSum(X, l, mid, r):
sum = 0
maxLeftSum = -sys.maxsize
for i in range(mid, l-1, -1):
sum = sum + X[i]
maxLeftSum = max(maxLeftSum, sum)
sum = 0
maxRightSum = -sys.maxsize
for i in range(mid+1, r+1):
sum = sum + X[i]
maxRightSum = max(maxRightSum, sum)
return maxLeftSum + maxRightSum
def findMaxSubarraySum(X, l, r):
if l == r:
return X[l]
else:
mid = l + (r-l)//2
leftMaxSum = findMaxSubarraySum(X, l, mid)
rightMaxSum = findMaxSubarraySum(X, mid+1, r)
crossingMaxSum = maxCrossingSum(X, l, mid, r)
return max(leftMaxSum, rightMaxSum, crossingMaxSum)
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 maximum subarray 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 easily get the max subarray sum of the whole array by finding the maximum value 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] denotes the maximum subarray sum ending at index i. If we know the maxSumEnding[i - 1], we can easily calculate the maxSumEnding[i]. Here are the insights:
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 store the solution of sub-problems and solve 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;
}
def findMaxSubarraySum(X, n):
maxSumEnding = [0] * n
maxSumEnding[0] = X[0]
for i in range(1, n):
if maxSumEnding[i - 1] > 0:
maxSumEnding[i] = X[i] + maxSumEnding[i - 1]
else:
maxSumEnding[i] = X[i]
maxSubarraySum = -sys.maxsize
for i in range(n):
maxSubarraySum = max(maxSubarraySum, maxSumEnding[i])
return maxSubarraySum
We are traversing array twice using single loop and performing O(1) operation at each iteration. Time complexity = O(n) + O(n) = O(n). Space complexity = O(n), for extra array maxSumEnd[n].
Now, let's address the critical questions: Can we solve this problem in O(1) space? Can we solve this problem in a single traversal? Here's an optimized solution idea using Kadane's algorithm.
So in this approach, we can use a single loop and two extra variables. This means there is no need for O(n) space or double traversal. So Kadane's algorithm is an optimized solution idea of the maximum subarray sum problem.
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 = std::max(maxsumEndingHere + X[i], X[i]);
if (maxsumSoFar < maxsumEndingHere)
maxsumSoFar = maxsumEndingHere;
}
return maxsumSoFar;
}
def findMaxSubarraySum(X, n):
maxsumSoFar = X[0]
maxsumEndingHere = X[0]
for i in range(1, n):
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!
Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.