Write a function to find the maximum sum of sub array where the array can have negative and positive numbers.

Question

Sigiloso · Accepted Answer

Don't jump to the answer. As some of you noticed, the question has ambiguties. Ask questions to clarify the question. They would like you to solve the problem after understanding all the details so that you won't miss any edge cases in your solution. Hint: The answer is recursive.

Brendan · Answer

In Python:

def largest_segment(s):
	y = 0
	z = 0
	for i in range(0, len(s)):
		y = max(y + s[i], 0)
		z = max(z, y)
	return z

Algorithm is O(n). Only works if the max value for an array containing all negatives is 0.

A · Answer

def maxSumSubArray(inputArray):
    currentSum = 0
    grandSum = 0
    for i in range(len(inputArray)):
        if (currentSum + inputArray[i]) < currentSum:
            currentSum = 0
            continue
        else:
            currentSum = currentSum + inputArray[i]
        if (grandSum < currentSum):
            grandSum = currentSum
    return grandSum

The Dude · Answer

answer in java:

		int array[] ={1,2,3,-6,5,6,9};
		table = new int[7][7];
		int i, j;
		int localMax = -999999999;
		for(i = 6 ; i >= 0 ; i--)
			for(j = i ; j < 7 ; j++)
			{
				if(i == j)
					table[i][j] = array[i];
				else
					table[i][j] = array[i] + table[i+1][j];
				localMax  = Math.max(localMax, table[i][j]);
			}
		System.out.println(localMax);

Microsoft

Pergunta de entrevista da empresa Microsoft

Respostas da entrevista

Empresas seguidas

Buscas de vagas