PS
BAN USER 0of 0 votes
AnswersEliminate all the anagrams from an Array of 100 Strings!
 PS in United States Report Duplicate  Flag  PURGE
Amazon Software Engineer Algorithm
The below code will give you max Sum in O(N).
We just have to get the startIndex and endIndex(when you make tempSum 0) and get the values inbetween them.
public static int maxSum(int[] numbers)
{
/*
* Handle Edge cases
* 1. is input Array is NULL
* 2. If input Array has only one element
*/
if(numbers == null)
{
return 1;
}
int maxSum = 0;
int tempSum = 0;
// int numbers[] = { 1 , 3 , 5 , 3 , 2 , 1 , 3 , 4 , 2 , 12 , 2 , 3}
// Iterating through the array 0...N
for(int i=0; i< numbers.length; i++)
{
// Adding it to temp Sum
tempSum = tempSum + numbers[i];
if(maxSum < tempSum)
{
maxSum = tempSum;
}
// If temp Sum is less than 0, making it to Zero.
// Ex: 1 + 3 + 5 = 1. In this case, making tempSum to Zero, so that 1 doesnt affect the sum of the next sequence
else if(tempSum < 0)
{
tempSum = 0;
}
}
return maxSum;
}

PS
February 09, 2016 I was asked this in an interview. I asked if I could sort it and the see if it is an arithmetic sequence or not (by calculating the difference between i+1 and i).
He didn't seem satisfied with the sorting approach. I tried to see if I can do something by calculating the min and max value  he said I am in the right direction. But unfortunately, I couldn't solve it and asked him for a hint. He gave me this:
(max  min)/(len  1) = difference
(70  10)/(7  1)
60/6 = 10
Its pretty straight forward to solve if the array can be stored.
Open Chat in New Window
 PS May 26, 2016