Microsoft Interview Question: 1- Given an array of integers... | Glassdoor

## Interview Question

Software Development Engineer (SDE) Interview(Student Candidate)

# 1- Given an array of integers, positive and negative. find

an interval in that array, whose elements constitutes the maximum sum

1

This is a fairly known problem, but I was too stressed at the time to think straight. first I offered a brute force solution through generating all intervals using 3 into one another for loops, with complexity O(n^3), but then he wanted to do it on O(n), he helped really alot but I didn't figure it out. anyway here's the solution

void calc( ) {
int input[] = {3, 5, -1, -5, 4,3, -3}
int sum = 0, largest = 0;
for (int i = 0; i largest) largest = sum;
}
cout &lt;&lt; largest;
}

This solution disregards the cases with all negative numbers, and empty array

moataz on Oct 5, 2012
1

Complete solution covering all -1 and returning the interval indexes:

int [] arr = {-123,-3,-9,-222,-44,-1,-66};

int currSeqLeft = 0;
int currSeqRight = 0;
int curr = arr[0];
int largestSeqLeft = 0;
int largestSeqRight = 0;
int largest = arr[0];

for (int i = 1; i = 0 ){
curr += arr[i];
currSeqRight = i;
}

if (curr &gt; largest) {
largest = curr;
largestSeqLeft = currSeqLeft;
largestSeqRight = currSeqRight;
}
}

System.out.println(largestSeqLeft + &quot;,&quot; + largestSeqRight);

ozitab on Nov 12, 2012
0

@moataz, that is not a good solution, it fails to identify the greater subinterval and also the maximum interval

Paul on Nov 18, 2012