Difficulty: Medium, Asked-in: Facebook, Microsoft, Amazon, Morgan Stanley, Walmart, Flipkart, Hike, Oracle, Samsung, Snapdeal, Zoho
Key takeaway
Given an array X[] with n elements, we need to write a program to find the maximum sum of a subarray among all subarrays. A subarray of array X[] is a contiguous segment from X[i] through X[j] where 0<= i <= j <= n.
Example 1
Input: X[] = [-4, 5, 7, -6, 10, -15, 3], Output: 16
Explanation: The subarray [5, 7, -6, 10] has the maximum sum.
Example 2
Input: X[] = [-3, 2, -1, 4,-2], Output: 5
Explanation: The subarray [2, -1, 4] has the maximum sum.
Example 3
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 the possible subarray for all i and j where i≤j. We calculate the sum of each subarray and return the maximum among them.
Solution Pseudocode
Time and space complexity analysis
We are using three nested loops : exploring all pairs in the outer two loops and calculating the running sum in the inner loop. Time complexity = O (n³). Space complexity = O(1)
Solution Idea
Now the critical question would be : can we optimize the above approach further? is it necessary to use the inner loop? Let’s think!
If we observe closely, we can calculate the sum of the sub-array from i to j+1 easily if we know the sum of the sub-array from i to j. So there is no need for an innermost loop to calculate the sum every time for each pair of (i, j). We can calculate the subarray sum using this formula Sum(i, j+1) = Sum(i, j) + X[j+1]. Using this formula, for every value of i, we can calculate the running sum for all values of j.
Solution Pseudocode
Time and space complexity analysis
There are only two nested loops in the above code. Time complexity = O(n²), Space complexity = O(1)
Again we should ask the same question: Can we improve the time complexity further? can we solve this problem using smaller sub-problems or the Divide & Conquer approach? Let's think!
Solution Idea
Suppose we want the maximum sub-array sum of the array X[l…r]. Let's divide the array into two equal subarrays — X[l…mid] and X [mid+1…r]. Then the maximum continuous sub-array X[i…j] must lie in one of the following places:
We can find the maximum sub-arrays of X[l…mid] and X[mid+1…r] recursively because these two sub-problems are smaller instances of the problem of finding a maximum sub-array sum. So now we need to calculate the maximum sub-array that crosses the mid-point and takes the maximum of all three possibilities.
Solution Pseudocode
Combine part implementation: maxCrossingSum(X, l, mid, r)
Sub-array crossing the mid-point comprises two sub-arrays, X[i…mid] and X[mid+1…j]. So we need to find the maximum sub-array form X[i…mid] and X[mid+1…j] and then combine them.
This idea works as follows:
Finally, we add maxleftSum + maxrightSum and return this value.
Time and space complexity analysis of divide and conquer approach
For simplifying the analysis, we assume that the original problem size is a power of 2, and T(n) is the time complexity of the max subarray of input size n. To calculate the overall time complexity, we need to add the time complexities of the divide, conquer, and combine parts.
Final recurrence relation: T(n) = O(1), if n=1, T(n) = 2 T(n/2) + O(n), if n>1
This recurrence is the same as a recurrence for merge sort. As we shall see from the master method, this recurrence has the solution T(n) = O(n logn). You might also revisit the recursion tree method of merge sort to understand why the solution should be O(n logn).
Space complexity = O(logn), for the stack space by recursive calls (Think!)
Solution Idea
Let’s take an array maxSumEnd[] of size n, where each maxSumEnd[i] denotes maximum subarray sum ending at index i. Now if we know the maxSumEnd[i-1], then we can easily calculate the maxSumEnd[i]. Here are insights:
Finally, we return the maximum value stored in the maxSumEnd[] array to find the solution. This problem falls under the dynamic programming strategy because we store the solution of sub-problems and solve the larger problem using the solution of a smaller sub-problem.
Solution Steps
Solution Pseudocode
Time and space complexity analysis
We are traversing the array twice using a single loop. So time Complexity = O(n). Space Complexity = O(n), for the extra array maxSumEnd[n]
Solution Idea
Now the critical question is: can we solve the problem in O(1) space? Furthermore, can we solve the problem in a single traversal? Here is the optimized solution using the famous kadane algorithm:
In the above idea, we are using two extra variables and one traversal. No extra space, No double traversal! It's an excellent optimization.
Solution steps
Solution Pseudocode
Time and space complexity analysis
Each element has been visited only once using a single loop. We are also doing constant operation at each step of iteration of the loop. So time complexity = O(n). Space complexity = O(1), we are using a constant number of variables only.
Enjoy learning, Enjoy coding, Enjoy algorithms!
Get well-designed application and interview centirc content on ds-algorithms, machine learning, system design and oops. Content will be delivered weekly.