Maximum Sum Subarray
Given an array of numbers, find the maximum sum of any contiguous subarray of the array.

For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, -5, and 86.

Given the array [-5, -1, -8, -9], the maximum sum would be -1.

Follow up: Do this in O(N) time.

Input Format:

The first line of input contains size of array, which is denoted by N and second line of input contains N space separated integers.

Output Format:

The first and only line of output should print the maximum subarray sum, as described in the description.

Question

Maximum Sum Subarray

Given an array of numbers, find the maximum sum of any contiguous subarray of the array.

For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, -5, and 86.

Given the array [-5, -1, -8, -9], the maximum sum would be -1.

Follow up: Do this in O(N) time.

Input Format:

The first line of input contains size of array, which is denoted by N and second line of input contains N space separated integers.

Output Format:

The first and only line of output should print the maximum subarray sum, as described in the description.

Accepted Answer

The direct approach to solve this problem is to run two for loops and for every subarray check if it is the maximum sum possible.
Time complexity: O(N^2), Where N is the size of the array.
Space complexity: O(1)

The efficient approach is to use Kadane's algorithm. It calculates the maximum sum subarray ending at a particular index by using the maximum sum subarray ending at the previous position.
Steps :
Declare two variables : currSum which stores maximum sum ending here and maxSum which stores maximum sum so far.
Initialize currSum = 0 and maxSum = INT_MIN.
Now, traverse the array and add the value of the current element to currSum and check :
1. If currSum > maxSum, update maxSum equals to currSum.
2. If currSum < 0, make currSum equal to zero.
Finally, print the value of maxSum.

Accepted Answer

Brute Force Approach

Create a nested loop. The outer loop will go from i = 0 to i = n - k. This will cover the starting indices of all k-subarrays
The inner loop will go from j = i to j = i + k - 1. This will cover all the elements of the k-subarray starting from index i
Keep track of the maximum element in the inner loop and print it.

Space Complexity: O(1)Explanation:

O(1) because the extra space being used (looping variables, maximum element) is constant for any N and K

Time Complexity: O(1)Explanation:

O(N * K) where N is the length of the input array and K is the size of the subarray.

Accepted Answer

BST Approach

Create a BST and insert the first k elements in it
Print the largest element in the tree
Now iterate through the remaining elements of the tree:
1. Insert the current element in the BST
2. Delete the one element that is not part of the current subarray
3. Print the largest element in the tree

Space Complexity: O(1)Explanation:

O(K) to store elements in the . At max, K elements will be stored

Time Complexity: O(1)Explanation:

O(N * log(K)) where N is the length of the input array and K is the size of the subarrays.

Accepted Answer

Deque Approach

Create a double ended queue. Note that the deque will store the indices of the elements, not the elements themselves
Insert the first k elements (the first subarray) in the deque. While inserting the current element, check if the element at the back of the queue is smaller than the current element. If yes, then remove all those elements and then insert the current element in the back of deque.
After you’ve done this, the front of the queue will have the maximum element in the first subarray. Print the front element of the deque.
Then, we’ll follow the same idea for the next elements as well but there will be one extra step which is to remove all elements from the front of the deque that are out of the range of the subarray in consideration.

Space Complexity: O(1)Explanation:

O(K) to store elements in the deque. At max, K elements will be stored

Time Complexity: O(1)Explanation:

O(N) where N is the length of the input array. We insert and delete every element in the array at most once and both these operations take O(1) time in case of a deque

Accepted Answer

1 person

Accepted Answer

The direct approach to solve this problem is to run two for loops and for every subarray check if it is the maximum sum possible. 
Time complexity: O(N^2), Where N is the size of the array.
Space complexity: O(1)

The efficient approach is to use Kadane's algorithm. It calculates the maximum sum subarray ending at a particular index by using the maximum sum subarray ending at the previous position. 
Steps : 
Declare two variables : currSum which stores maximum sum ending here and maxSum which stores maximum sum so far.
Initialize currSum = 0 and maxSum = INT_MIN.
Now, traverse the array and add the value of the current element to currSum and check : 
1. If currSum > maxSum, update maxSum equals to currSum.
2. If currSum < 0, make currSum equal to zero.
Finally, print the value of maxSum.

Reply

2y

Brute Force ApproachCreate a nested loop. The outer loop will go from i = 0 to i = n - k. This will cover the starting indices of all k-subarraysThe inner loop will go from j = i to j = i + k - 1. Thi...
see more

Reply

2y

BST ApproachCreate a BST and insert the first k elements in itPrint the largest element in the treeNow iterate through the remaining elements of the tree:Insert the current element in the BSTDelete th...
see more

Reply

2y

Deque ApproachCreate a double ended queue. Note that the deque will store the indices of the elements, not the elements themselvesInsert the first k elements (the first subarray) in the deque. While i...nonymously

Given an array of numbers, find the maximum sum of any contiguous subarray of the array.

For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, -5, and 86.

Given the array [-5, -1, -8, -9], the maximum sum would be -1.

Follow up: Do this in O(N) time.

Input Format:

The first line of input contains size of array, which is denoted by N and second line of input contains N space separated integers.

Output Format:

The first and only line of output should print the maximum subarray sum, as described in the description.

Top Tech Mahindra Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in Tech Mahindra Software Engineer