Google Interview Questions Part 1

A friend of mine was interview for a position in Google, he got this hard question asked:

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

Let see you solve this problem in few minutes...

In the next post I would publish the solution