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 in-between 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;
}
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.
- PS May 26, 2016