Related tags:

dynamic-programmingdivide-and-conquersingle-loopmicrosoft-interview-questionsgoogle-interview-questionsamazon-interview-questionscoding-interview-questions**Difficulty:** Medium, **Asked-in:** Facebook, Microsoft, Amazon, Morgan Stanley, Walmart, Flipkart, Hike, Zoho

**Key takeaways**

- One of the best problems to learn time and space complexity optimization using several approaches.
- The idea of
**the Kadane Algorithm**is intuitive and worth exploring. We can use a similar concept to solve several other coding problems efficiently.

Given array X[] of n integers, write a program to find the maximum sum of 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 array contains all non-negative numbers, the maximum subarray sum would be the sum of entire array.
- Several different sub-arrays may have the same max sum, but we just need to return the value of 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 non-negative. So the maximum subarray sum would be the sum of the entire array.

- 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 : Using single loop and O(n) space
- Kadane algorithm: Using single loop and variables

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.

- We declare variable
**maxSubarraySum**to store the max subarray sum found so far. -
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.

- For each subarray, we run another loop from k = i to j and calculate sub-array sum between them. We store this value in variable
**subarraySum**. **If (subarraySum > maxSubarraySum)**, we update maxSubarraySum with subarraySum.

- For each subarray, we run another loop from k = i to j and calculate sub-array sum between them. We store this value in variable
- By the end of nested loop, we return maxSubarraySum
**.**

```
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
}
```

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)

Explore this 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 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
}
```

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²)

- At each iteration, we perform constant number of operations. Time complexity = Total count of loop iterations * O(1) = O(n²)
- We are using constant extra space. Space complexity = O(1)

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:

- 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 mid-point, where
**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 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].

- 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!

```
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)
}
```

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.

- For base case (n = 1), algorithm takes constant time. T(1) = O(1).
- The time complexity of divide part is O(1), because we only need to calculate mid to divide 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 overall time complexity of the conquer part = 2T(n/2).
- To find the max subarray sum crossing the mid-value, we run two separate single loops in the opposite direction. In the worst case, each loop runs n/2 times. So 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 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:

- 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]. We update, maxSumEnding[i] = maxSumEnding[i - 1] + X[i]**If (maxSumEnding[i -1] < 0)**, we need to ignore maxSumEnding[i -1] to calculate maxSumEnding[i], because maxSumEnding[i - 1] + X[i] will be less than X[i]. 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 array maxSumEnding[].

This problem falls under the dynamic programming strategy because we store the solution of sub-problems and solve the larger problem using solution of smaller sub-problems.

- We create an extra array maxSumEnding[] of size n.
- We initialize array with the first value i.e. maxSumEnding[0] = X[0]
- Now we traverse array from i = 1 to n - 1. 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 maximum stored in maxSumEnding[].

```
int getMaxSubarraySum (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 = 0
for (int i = 0; i < n; i = i + 1)
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:

- 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 max subarray sum will be the maximum of all subarray sums ending at index i. 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.** - At each iteration of the single loop,
**if (maxsumEndingHere > maxsumSoFar)**, we update**maxsumSoFar = maxsumEndingHere.** - By the end of loop, the maximum subarray sum value gets stored in variable
**maxsumSoFar**. We return this value as an output.

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.

- We initialize variables
**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 i.e
**maxsumEndingHere = max (maxsumEndingHere + X[i], X[i]).** - We also update maxsumSoFar i.e.
**if(maxsumSoFar < maxsumEndingHere), maxsumSoFar = maxsumEndingHere.** - By the end of loop, we return
**maxsumSoFar**.

```
int getMaxSubarraySum (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 single loop and doing constant operation. Time complexity = O(n). Space complexity = O(1), we are using constant number of variables.

- 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 of solving 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 a sorted array is provided as an input?
- Can we use a similar approach to find the max product subarray?

- 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)

- Find the maximum product subarray
- Find the sum of the maximum elements of every possible sub-array
- The longest subarray in a binary array with an equal number of 0s and 1s
- Largest sum contiguous subarray having only non-negative elements
- Product of Array Except Self
- Max Consecutive Ones
- Number of buildings facing the sun

**Enjoy learning, Enjoy coding, Enjoy algorithms!**

Find Product of Array Except Self

Given an array X[] of n integers, write a program to find an array product[] such that product[i] is equal to the product of all the elements of X[] except X[i]. We need to solve this problem without using division operations. This is an excellent problem to learn problem-solving using prefix array and a single loop.

Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.