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

Question

Anonymous · 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

Microsoft Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches