Find the maximum subset sum in an array of numbers. Discuss complexity.

Question

ali · Accepted Answer

I assume you mean sub sequence, not subset.

It can be solved in linear time but using a cumulative array instead of the original one.
e.g. 4 8 -2 4 0 0 3 5 -30 12
4 12 10 14 14 14 17 22 -8 4
find the max number and the min number before that 
4 - 22
the max sum sub sequence are between these indicies and max value is the max sum

Dim · Answer

I think they asked about Maximum subarray problem:
http://en.wikipedia.org/wiki/Maximum_subarray_problem

blakdogg · Answer

I assume you mean sub sequence, not subset.

e.g. 4 8 -2 4 0 0 3 5 -30 12
the max subset would be, 
 4 8  4 0 0 3 5 12 = 34
but the max sub sequence would be 
4 8 -2 4 0 0 3 5  = 22

you would need to track the start point of the current subsequence and its sum, when the sum becomes negative you would start a new subsequence and update the current max subsequence.

Amazon

Amazon Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches