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

Pergunta de entrevista da empresa Microsoft

Respostas da entrevista

Empresas seguidas

Buscas de vagas