Difficulty: Medium, Asked-in: Facebook, Microsoft, Amazon, Morgan Stanley, Walmart, Flipkart, Hike, Zoho
Key takeaways
Given array X[] of n integers, write a program to find the maximum sum of subarray among all subarrays.
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 would be to explore all the possible subarray for all i and j, where i ≤ j. We calculate sum of each subarray and return the maximum among them.
Now we explore all subarray (i, j) using nested loop: outer loop run from i = 0 to n - 1 and inner loop run from j = i to n - 1.
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. Time complexity = O (n³). Space complexity = O(1). Note: Explore analysis of loop blog for analyzing such type of loop.
Now critical questions are : can we optimize the above approach further? Is it necessary to use the innermost loop from k = i to j? Let’s think!
If we observe closely, we can easily calculate 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 optimized version of the above approach, where we run only two nested loops: outer loop picks the starting index, and inner loop calculates running sum of all sub-arrays starting from that index. So we avoid an extra inner loop to calculate sum for every i and j.
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
There are only two nested loops in the above code. Total count of nested loop iterations = n + n - 1 + n - 2 + ... + 2 + 1 = n(n + 1)/2 = O(n²)
Now critical questions are: can we improve time complexity further? can we solve this problem using smaller sub-problems or divide and conquer approach? Let's think!
Before moving forward with this approach, we recommend exploring merge sort first.
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.
Let's divide the array into two equal subarrays by calculating mid-index: X[l ... mid] and X [mid + 1 ... r]. Here sub-array X[i … j] with 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 sub-problems are smaller instances of the same problem of finding maximum sub-array sum.
int leftMaxSum = findMaxSubarraySum (X, l, mid)
int rightMaxSum = findMaxSubarraySum (X, mid + 1, r)
So now we need to calculate the maximum sub-array that crosses the mid-point and takes the maximum of all three possibilities.
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 max subarray sum as X[l] or X[r]. This would be the smallest version of the problem, where 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)
}
}
Sub-array crossing the mid-point comprises two sub-arrays: X[i…mid] and X[mid + 1…j]. So we need to find the max sub-array sum from X[i…mid] and X[mid + 1…j] and combine them. The idea works as follows:
Step 1: Find the maximum contiguous sum of the left half X[l…mid].
Since this subarray must contain X[mid]. So we run a loop starting from index i = mid to l, calculate the contiguous sum and store it in the variable sum. Whenever sum > maxLeftSum, we update maxLeftSum with sum.
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: Find the maximum contiguous sum of the right half X[mid + 1 ... r].
Now we run a loop starting from the index j = mid + 1 to r, calculate the continuous sum and store it in the variable sum. Whenever sum > maxRightSum, we update maxRightSum with 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
}
Step 3: Finally, to get the maximum contiguous subarray sum crossing the mid, we return the sum of variables maxLeftSum and maxRightSum. Think!
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 (i = mid + 1; i <= r; i = i + 1)
{
sum = sum + X[i]
if (sum > maxRightSum)
maxRightSum = sum
}
return (maxLeftSum + 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)
For simplifying the analysis, we assume that input size n is a power of 2, and T(n) is the time complexity of finding the max subarray sum. To calculate the overall time complexity, we need to add the time complexities of the divide, conquer, and combine parts.
Final recurrence relation:
This is the same as a recurrence for merge sort, so overall time complexity = O(nlogn). You can revisit merge sort time complexity analysis using the recursion tree or master method or analysis of recursion using master theorem.
Space complexity is equal to the size of recursion call stack, which depends on the height of the recursion tree. At each stage, input size decreases by 2, so the height of recursion tree will be O(logn). Space complexity = O(logn). Think!
Let’s take an array maxSumEnding[] of size n, where maxSumEnding[i] denotes maximum subarray sum ending at index i. If we know the maxSumEnding[i - 1], we can easily calculate the maxSumEnding[i]. Here are some insights:
This problem falls under dynamic programming because we store the solution of sub-problems and solve the larger problem using the solution of smaller sub-problems.
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 critical questions are: can we solve the problem in O(1) space? Can we solve the problem in a single traversal? Here is an optimized solution idea using the famous kadane algorithm:
In the above idea, we are using single loop and two extra variables. So no extra space, no double traversal! It's an excellent optimization.
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 single loop and doing constant operation. Time complexity = O(n). Space complexity = O(1), we are using constant number of variables.
Enjoy learning, Enjoy coding, Enjoy algorithms!
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.