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
|