Simplistic Thinking

I recently came across a Google interview questions that kind of intrigued me. It went like this:

"You have a list of numbers which some of them are negative and some of them are positive, find out the largest sum of sequential subset of numbers from this list."

For example:

-5, 20, -4, 10, -18

The solution is the subset [20, -4, 10] which its sum is 26

The solution for this question is not summary the positive numbers or sort the list because the subset needs to be sequential.

A possible not efficient answer would be to to calculate the summary of all the possible subsets in the list but the complexity of this solution is O(N^2)

However the interviewer wanted a solution of O(N) !!!

This question is so full of subtleties that it cannot fail to entice even the most interview savvy reader. In order to be able to properly answer this question the interviewee not only has to understand big O, but also this particular type of problem. One brilliant aspect of the question is that it already contain parts of the answer. The answer can be found in the requested solution of O(N). This ought to give enough information on how the algorithm should be structured (or should it?)

O(N^2) solution (Groovy)

This solution illustrates a simple solution to this problem with O(N^2) complexity in Groovy.

def findLargestSubSequence(seq)
{
def tmpSeq = [], maxSeq = []
def maxVal = -9999999

seq.eachWithIndex { val, index ->
seq[index..seq.size()-1].eachWithIndex { innerVal, innerIndex ->
tmpSeq = sequence[index..innerIndex]
if(tmpSeq.sum() > maxVal) {
maxVal = tmpSeq.sum()
maxSeq = tmpSeq
}
}
}
maxSeq // no return needed, value is returned automatically
}

println findLargestSubSequence([-5, 20, -4, 10, -18])

And the O(N^2) comes from the nested iterations of course :)

O(N) solution

This solution illustrates one (not simple) solution to this problem with O(N) complexity in Java.

int[] findLargestSubSequence(int[] sequence)
{

int mini = -1, minv = 0, maxi1 = 0, maxi2 = 0, maxv = -9999999;
int[] seq = sequnce.clone();

for(int i = 0; i <> {

if (i > 0) {
seq[i] += seq[i-1];

}
if (seq[i]-minv >= maxv) {
maxv = seq[i] - minv;
maxi1 = mini + 1;
maxi2 = i;
}
if (seq[i] < minv) {
minv = seq[i];
mini = i;
}

}
return getSubArray(seq, maxi1, maxi2); // you have to write this :)
}

Here we see that there is only one iteration. The code is pretty hard to read though as it relies on a rewriting patterns where the path towards the solution is driven by successive alteration to the source input.