• Given an array of integers. Find the LARGEST subarray with the MAXIMUM sum. Try doing it in linear time?

Again one of the favourite Microsoft/Google questions particularly because of the requirement to do the question in linear time i.e. in a single loop. Let's start with an example below. Pay special attention to the two words LARGEST and MAXIMUM. If you remove the LARGEST or change it to SMALLEST the question totally changes.

One way interviewers figure if you have already heard of the question is if you don't show concern for the largest because they are very important adjectives for this question. To show you why it matters consider the example below

If we just want the subarray with the maximum sum then that consists of the first two elements i.e. 4 and 5 with a sum of 9

If we want the LARGEST subarray with the maximum sum then that would be the entire array i.e. all the elements consisting of 4, 5, -2 and 1, since that's the LARGEST subarray with a sum of 8.

Note the order of the priorities, i.e. largest has precedence over maximum. That is we start listing out the largest sub-arrays and stop at the one with the maximum sum. However if it the other way round i.e. maximum had precedence over largest then our presented algorithm would fail.

It's a good idea if you would try to work the variations of this question as this question becomes more and more common interviewers are likely to tweak it.

Let's start with our algorithm now.

The most basic solution is brute force. List out all the possibilities of sub-arrays you can have and find the sub-array with the greatest sum and longest length. However there's a better way to crack this question.

Here's the core trick. Note that the sub-array will be contiguous i.e. the sub-array would consist of consecutive cells of the original array. There can be NO gaps. Though this is very obvious but neglecting this subtle restriction can lead you astray.

Let's start with the first cell which has the number 2. Say we have a variable called SUM initialized to zero. We also have two variables SB_START and SB_END to indicate the start and end of the best subarray we find. We set SB_START = 0. Now note that the next cell has 5. Should we include it in our sub array or not ? Well the new sum would be 7 which is greater than 2 and we would have a bigger sub-array so we should go ahead and add 5 to our SUM variable.

However what would have happened if we had a -5?

The new sum would have been -3 which is less than the previous value of our variable SUM = 2. We would have been better off just keeping our sub-array restricted to the first cell containing 2. This is the crucial point i.e. deciding when to add the next consecutive cell to the subarray. Adding the next cell to the subarray is feasible only if it would not decrease the total sum below zero. If the sum is decreased but stays above or equal to zero, we don't mind as explained below.

Note the word 'below' zero; not equal to zero. If the sum went below zero, it would not make sense to add the next consecutive cell of the array to our subarray so we stop at there and simply note the sum of the scanned sub-array. Next we skip the negative number i.e. -5 and start on with a new sub array starting at 1.

This is our cue then. We keep summing elements and increasing our subarray by incrementing SB_END until we drop below zero on addition of a negative number. we stop just short of the negative number and record the end of the subarray we just traversed. Next we compare our SUM to bestSUM which might be used to store the maximum sum seen so far for the subarrays. If SUM > bestSUM then we update bestSUM = SUM and save SB_END and SB_START. Next we skip the negative number on which we had stopped and repeat our algorithm.

To make the idea more concrete. Consider the following array.

Some might answer that the largest sub-array starts from cell containing 1 and ends at cell containing 9. This isn't true reason being that we are asked to find the largest sub-array with the maximum sum. If we don't include the first two elements which sum up to zero we will be returning a subarray which is two less in length than if we returned the entire array. Note that if we switch -7 and 7 then our largest subarray doesn't consist of the first element because it is only bringing our total sum down. We can convieniently disregard it. However we couldn't do so in the previous case because of the contiguous requriement i.e. the subarray had to be contiguous and longest.

You can mention the special cases to the interviewer. In an array with all negative numbers, the least negative number would consist of a single cell sub array with the largest sum. Similarly an array of all positive numbers including zeros will itself form the largest subarray.