Amazon Interview Question
Software Engineer / Developersthe question is asked in most of the IT interviews. This is a simple solution,
def max_subarray(A):
max_so_far = max_ending_here = 0
print "max ending here, max so far"
for x in A:
max_ending_here = max(0, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
print max_ending_here, max_so_far
return max_so_far
if __name__ == "__main__":
A = [2, 4, -8, 10, -1, 5]
print max_subarray(A)
B = [2, -3, 10, -8, 9, -4, 1, -7]
print max_subarray(B)
for O(n) complexity:
- bindas September 01, 2008Kadane's algorithm /* maximum subarray a[k..l] of a[1..n] */
(k; l) := (0; 0); s := -inf; t := 0; j := 1;
for i:=1 to n do begin
t := t + a[i];
if t > s then begin (k; l) := (j; i); s := t end;
if t < 0 then begin t := 0; j := i + 1 end
end