Interview Questions

Given a n array of positive and negative integers, find the subarray with max sum in O(n) and one loop.

Software QA/Tests Interview Questions from Microsoft


(Continued from previous question...)

Given a n array of positive and negative integers, find the subarray with max sum in O(n) and one loop.

Q:
Microsoft Interview Question for Software Engineer in Tests about Algorithm
Given a n array of positive and negative integers, find the subarray with max sum in O(n) and one loop.


A:
Supose S is the array of integers, N the length and sum the current sum. Let best be the solution at current step.We keep in x and y the limit of the best array
Initally,best = -INF and sum = 0.
Then

for(i = 0 ;i < N ; ++i)
{
if(sum <= 0) {sum = S[i] ; idx = i; }
else sum += S[i];
if(best < sum) {best = sum;x = idx ; y = i;}


The solution will be the subarray [x,y]. Complexity O(N) time O(1) memory and one loop.

(Continued on next question...)

Other Interview Questions