1- Given an array of integers, positive and negative. find an interval in that array, whose elements constitutes the maximum sum

Question

ozitab · Accepted Answer

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 > largest) {
			 largest = curr;
			 largestSeqLeft = currSeqLeft;
			 largestSeqRight = currSeqRight;
		 }
	 }
	 
	 System.out.println(largestSeqLeft + "," + largestSeqRight);

moataz · Answer

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 << largest;
}

This solution disregards the cases with all negative numbers, and empty array

Paul · Answer

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

Microsoft

Microsoft Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches