Difficulty: Medium, Askedin: Facebook, Microsoft, Amazon, Morgan Stanley, Walmart, Flipkart, Hike, Zoho
Key takeaway
 One of the best problems to optimization using several approaches.
 The idea of Kadane's Algorithm is intuitive and worth exploring. We can use a similar idea to solve a lot of other coding problems efficiently.
Let’s understand the problem
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] through X[j]. where 0 <= i <= j <= n.
 If the array contains all nonnegative numbers, the maximum subarray sum would be the sum of the entire array.
 Several different subarrays may have the same max sum but we need to just return the value of the max subarray sum.
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 nonnegative. So the maximum subarray sum would be the sum of the entire array.
Discussed solution approaches
 A brute force approach using three nested loops
 Using two nested loops
 Using divide and conquer idea similar to the merge sort
 Using dynamic programming
 Kadane algorithm: Using single loop and variables
A brute force approach using three nested loops
Solution Idea
The most basic solution would be 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 Steps
 We declare a variable maxSubarraySum to store the max subarray sum found so far.

Now we explore all subarray (i, j) using a nested loop: outer loop run from i = 0 to n  1 and inner loop run from j = i to n  1.
 For each subarray, we run another loop from k = i to j and calculate the subarray sum between them. We store this value in a variable subarraySum.
 Now if we find subarraySum > maxSubarraySum, we update maxSubarraySum with subarraySum.
 By end of the nested loop, we return maxSubarraySum.
Solution Pseudocode
int getMaxSubarraySum (int X[], int n)
{
int maxSubarraySum = 0
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
}
Solution Analysis
We are using three nested loops : exploring each subarray using the outer two loops and calculating their sum using the inner loop. Time complexity = O (n³). Space complexity = O(1)
Explore this blog for analyzing such type of loop: https://www.enjoyalgorithms.com/blog/timecomplexityanalysisofloopinprogramming
Using two nested loops
Now the critical question would be : can we optimize the above approach further? is it necessary to use the innermost loop from k = i to j? Let’s think!
Solution Idea
If we observe closely, we can calculate the subarray sum from i to j + 1 easily in O(1), if we know the subarray 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]. Think!
This is the optimized version of the above approach, where we only run two nested loops: the outer loop picks the starting index and the inner loop calculates the running sum of all subarrays starting from that index. So we are avoiding the extra inner loop to calculate the sum for every i and j.
Solution Pseudocode
int getMaxSubarraySum (int X[], int n)
{
int maxSubarraySum = 0
for (int i = 0; i < n; i = i + 1)
{
subarraySum = 0
for (int j = i; j < n; j = j + 1)
{
subarraySum = subarraySum + X[j]
if (subarraySum > maxSubarraySum)
maxSubarraySum = subarraySum
}
}
retun maxSubarraySum
}
Solution Analysis
 There are only two nested loops in the above code. Total number of nested loop iterations = n + n  1 + n  2 + ... + 2 + 1 = n(n+1)/2 = O(n²)
 At each iteration, we are performing a constant number of operations i.e. O(1) operations. So time complexity = Total count of loop iterations * O(1) = O(n²)
 We are using constant extra space. So, space complexity = O(1)
Using divide and conquer idea similar to merge sort
Again we should ask the same question: can we improve the time complexity further? can we solve this problem using smaller subproblems or the divide & conquer approach? Let's think! But before exploring this approach, we recommend exploring the idea of merge sort.
Solution Idea
Suppose we want to calculate the maximum subarray sum of the array X[l … r], where l and r are the left and right end of the input array.
Let's divide the array into two equal subarrays by calculating the midindex: X[l ... mid] and X [mid + 1 ... r]. Then the subarray X[i … j] with maximum sum must lie in one of the following places:
 Entirely in the left subarray X[l…mid], where l ≤ i ≤ j ≤ mid.
 Entirely in the right subarray X[mid+1…r], where mid+1 ≤ i ≤ j ≤ r
 Subarray crossing the midpoint, so that low ≤ i ≤ mid ≤ j ≤ r. This includes some rightmost elements of the left subarray and some leftmost elements of the right subarray.
We can recursively find the maximum subarray sum of X[l…mid] and X[mid + 1…r] because these two subproblems are smaller instances of the same problem of finding a maximum subarray sum.
int leftMaxSum = findMaxSubarraySum (X, l, mid)
int rightMaxSum = findMaxSubarraySum (X, mid + 1, r)
So now we need to calculate the maximum subarray that crosses the midpoint 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.
Solution Pseudocode
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)
}
}
Combine part implementation: maxCrossingSum(X, l, mid, r)
Solution Idea
Subarray crossing the midpoint comprises two subarrays: X[i…mid] and X[mid + 1…j]. So we need to find the max subarray sum from X[i…mid] and X[mid + 1…j] and then combine them. The idea works as follows:
Step 1: find the maximum contiguous sum of the left half X[l…mid].
 We initialize a variable sum to store the continuous sum from mid to some index i.
 We initialize a variable maxLeftSum to store the max sum found so far.

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].
 We use the same variable sum and initialize it with 0.
 We initialize a variable maxRightSum to store the max sum found so far.

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!
Solution Pseudocode: finding max subarray sum crossing the mid
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)
}
Time and space complexity analysis of divide and conquer approach
For simplifying the analysis, we assume that the 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.
 For the base case (n = 1), the algorithm takes constant time. T(1) = O(1). The recursive case occurs when n > 1.
 The time complexity of the divide part is O(1) because we only need to calculate the mid to divide the array into two halves.
 The input size of each subproblem is n/2, so we need to spend T(n/2) time solving each. We are solving two subproblems of size n/2, so the overall time complexity of the conquer part = 2T(n/2).
 To find the max subarray sum crossing the midvalue, we run two separate single loops in the opposite direction. In the worst case, each loop runs n/2 times. So the time complexity of the combine part = O(n).
Final recurrence relation:
 T(n) = O(1), if n = 1
 T(n) = 2 T(n/2) + O(n), if n > 1
This is the same as a recurrence for merge sort, so overall time complexity = O(nlogn). You can revisit the merge sort analysis using the recursion tree or master method.
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). So space complexity = O(logn). Think!
Using dynamic programming
Solution Idea
Let’s take an array maxSumEnding[] of size n, where each maxSumEnding[i] denotes maximum subarray sum ending at index i. Now if we know the maxSumEnding[i  1], then we can easily calculate the maxSumEnding[i]. Here are some insights:
 maxSumEnding[i] always include the value X[i].
 If (maxSumEnding[i  1] > 0), we need to include maxSumEnding[i  1] to calculate maxSumEnding[i] because maxSumEnding[i  1] + X[i] will be greater than X[i]. So we update, maxSumEnding[i] = maxSumEnding[i1] + X[i]
 If (maxSumEnding[i 1] < 0), we need to ignore maxSumEnding[i 1] to calculate maxSumEnding[i] because maxSumEnding[i] because maxSumEnding[i  1] + X[i] will be less than X[i]. So we update, maxSumEnding[i] = X[i]
 In more simple way, we can write: maxSumEnding[i] = max (maxSumEnding[i  1] + X[i], X[i])
 Finally, to get the max subarray sum of the whole array, we need to return the maximum value stored in the array maxSumEnding[].
This problem falls under the dynamic programming strategy because we store the solution of subproblems and solve the larger problem using the solution of a smaller subproblem.
Solution Steps
 We create an extra array maxSumEnding[] of size n.
 We initialize the array with basic solution i.e. maxSumEnding[0] = A[0]
 Now we traverse the array from i = 1 to n  1. Here at any ith iteration, we calculate the max subarray sum ending at index i and store it at position maxSumEnding[i].
 If (maxSumEnding[i  1] < 0), maxSumEnding[i] = X[i]
 Else, maxSumEnding[i] = X[i] + maxSumEnding[i  1]
 We return the max of sum stored in the maxSumEnding[] array.
Solution Pseudocode
int getMaxSubarraySum (int X[], int n)
{
int maxSumEnding[n]
maxSumEnding[0] = X[0]
for (int i = 1; i <n; i = i + 1)
{
if (maxSumEnding[i1] > 0)
maxSumEnding[i] = X[i] + maxSumEnding[i1]
else
maxSumEnding[i] = X[i]
}
int maxSubarraySum = 0
for (int i = 1; i <n; i = i + 1)
maxSubarraySum = max (maxSubarraySum, maxSumEnding[i])
return maxSubarraySum
}
Solution Analysis
We are traversing the array twice using a single loop and performing an O(1) operation at each iteration. So time complexity = O(n) + O(n) = O(n). Space Complexity = O(n), for the extra array maxSumEnd[n].
An efficient approach using the Kadane algorithm
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:
 According to the above approach, we can easily calculate the max subarray sum ending at ith index using the max subarray sum ending at (i 1)th index. So we can update this value in a loop using some variable. Let's say this variable is maxsumEndingHere.
 The value of the max subarray sum will be the maximum of all the subarray sums ending at index i. So we can track this value in a variable using the same loop where we are calculating the maxsumEndingHere. Let's say this variable is maxsumSoFar.
 So at each iteration of the single loop, if (maxsumEndingHere > maxsumSoFar), we update maxsumSoFar = maxsumEndingHere.
 By the end of the loop, the maximum subarray sum value gets stored in the variable maxsumSoFar. We return this value as an output.
In the above idea: we are using a single loop and two extra variables. So no extra space, no double traversal! It's an excellent optimization.
Solution steps
 We initialize the variable maxsumSoFar and maxsumEndingHere with X[0].
 Now we run a loop from i = 1 to n 1. At each ith iteration:
 We calculate max subarray sum ending at the ith index in i.e maxsumEndingHere = max (maxsumEndingHere + X[i], X[i]).
 We also update maxsumSoFar i.e. if(maxsumSoFar < maxsumEndingHere), maxsumSoFar = maxsumEndingHere.
 By end of the loop, we return maxsumSoFar.
Solution Pseudocode
int getMaxSubarraySum (int X[], int n)
{
int maxsumSoFar = X[0]
int maxsumEndingHere = X[0]
for (i = 1 to n1)
{
maxsumEndingHere = max (maxsumEndingHere + X[i], X[i])
if(maxsumSoFar < maxsumEndingHere)
maxsumSoFar = maxsumEndingHere
}
return maxsumSoFar
}
Solution Analysis
We are traversing each once using a single loop and doing constant operation at each iteration. So time complexity = O(n). Space complexity = O(1), we are using a constant number of variables only.
Critical ideas to think!
 How can we modify the above approaches to find the start and end indices of the subarray with maximum sum?
 Do the above algorithms handle the case of negative numbers?
 Can we think to solve this problem using some other approaches?
 How can we design a solution to calculate the maximum sum submatrix of size k x k in the m x n matrix?
 How do we solve the problem if the sorted array is provided as an input?
 Can we use a similar approach to find the max product subarray?
Comparisons of time and space complexities
 Three nested loops: Time = O(n^3), Space = O(1)
 Two nested loops: Time = O(n^2), Space = O(1)
 Divide and Conquer: Time = O(nlogn), Space = O(logn)
 Dynamic Programming: Time = O(n), Space = O(n)
 Kadane Algorithm: Time = O(n), Space = O(1)
Suggested coding questions to practice
Enjoy learning, Enjoy coding, Enjoy algorithms!