## Amazon Interview Question

SDE-2s**Country:**India

**Interview Type:**Phone Interview

We do not need 'nlogn', we only need O(n). As mentioned above, it is a Kadane Algorithm.

```
int length ;
int a[]={-12, 14, 0, -4, 61, -39};
length = a.length;
int absoluteMax=0, localMax=0, startIndex=0, lastIndex=0, tempStartIndex=0;
for (int index = 0; index < length;index++) {
localMax= localMax + a[index];
if(localMax < 0){ localMax=0; tempStartIndex = index + 1;}
if(absoluteMax < localMax) {
absoluteMax = localMax;
lastIndex = index;
startIndex = tempStartIndex;
}
}
```

Hi Raaz,

Can u please clarify this

P = {4,6,-3,1,5,9,-2} is the array

S ={1,5,9} has sum of 15

but Q = {4,6,-3,1,5,9} has sum of 22.

so is S is correct or Q...?

First thought is brute force, that thats just a start.

Second thought would be to think of the array as the bottom tier of a quasi-binary tree, building up towards the final sum as the 'root' of the tree.

You could then walk the tree from the root, looking at each individual tier, looking for the maximal node combination

```
//linear time O(n), traverse from left to right
//initialize variables
int i = 0;
int maxSum = 0; // sum of current maximum array
int LastSum = 0; // sum of current extending array
int maxBegin = 0; //start position of current maximum array
int LastBegin = 0; //start position of current extending array
int maxLength = 1; // length of current maximum array
int LastLength = 1; // length of current extending array
for(i=0; i<arr.length(); i++)
{
//if LastSum and the current integer are both non-negative or LastSum >= |arr[i]|, merge them
if(LastSum >= 0 && (arr[i] >= 0 || LastSum >= -arr[i]))
{
LastSum += arr[i];
LastLength ++;
}
//if arr[i] < 0, and |arr[i]| > LastSum , restart the calculation
else if arr[i] < -LastSum //note that LastSum is maintained non-negative
{
LastLength = 0;
LastSum = 0;
if(i< arr.length)
LastBegin = i+1;
}
///compare LastSum and maxSum, if LastSum is greater, update the array which has maximum sum.
if( LastSum >= maxSum )
{
maxSum = LastSum;
maxBegin = LastBegin;
maxLength = LastLength;
}
}
```

This is called Maximum Sub Array problem (refer MIT Introduction to Algorithms by Cormen)

```
public class MaxSubArray {
private static class SubArray {
int start;
int end;
int sum;
SubArray(int start, int end, int sum) {
this.start = start;
this.end = end;
this.sum = sum;
}
}
private SubArray findMaxCrossingSubArray(int[] data, int start, int mid,
int end) {
int sum = 0;
int leftSum = Integer.MIN_VALUE;
int maxLeft = mid;
for (int index = mid; index >= start; index--) {
sum += data[index];
if (leftSum < sum) {
leftSum = sum;
maxLeft = index;
}
}
int rightSum = Integer.MIN_VALUE;
int maxRight = mid + 1;
sum = 0;
for (int index = mid + 1; index <= end; index++) {
sum += data[index];
if (rightSum < sum) {
rightSum = sum;
maxRight = index;
}
}
return new SubArray(maxLeft, maxRight, leftSum + rightSum);
}
public SubArray findMaxSubArray(int[] data, int start, int end) {
if (start == end)
return new SubArray(start, end, data[start]);
int mid = (start + end) / 2;
SubArray ls = findMaxSubArray(data, start, mid);
SubArray rs = findMaxSubArray(data, mid + 1, end);
SubArray mcs = findMaxCrossingSubArray(data, start, mid, end);
if (ls.sum >= rs.sum && ls.sum >= mcs.sum)
return ls;
else if (rs.sum >= ls.sum && rs.sum >= mcs.sum)
return rs;
else return mcs;
}
public static void main(String[] args) {
int[] data = { -9, 3, 3, 4, 3, -7, -5, 1, -2, 5, 4, 2, -5, 4 };
MaxSubArray msa = new MaxSubArray();
SubArray sa = msa.findMaxSubArray(data, 0, data.length - 1);
System.out.println("Start: " + sa.start + ", End: " + sa.end + ", Sum: "
+ sa.sum);
}
}
```

The code runs in O(n log n)

dp

```
public static void findMaxSeq(int [] seq){
int [] dp = new int [seq.length] ;
dp [0] = seq [0] ;
int max = Integer.MIN_VALUE ;
int end = -1 ;
int start = -1 ;
for (int i = 1 ; i < seq.length ; ++i){
if (seq[i] + dp[i-1] <= 0 ){
dp [i] = seq[i] ;
}else{
dp [i] = seq[i] + dp[i-1] ;
}
if (dp[i] > max){
max = dp [i];
end = i;
}
}
end = dp [0] > max ? 0 : end;
for (int i = 0 ; i < dp.length ; ++i){
if (dp[i] >= 0){
start = i ;
break;
}
}
System.out.println("from " + start + " to " + end);
```

}

```
o(n) solution, in two passes we should be able to find the max sub array without disturbing the sequence
public static void maxSubArray(int[] arr)
{
int cummaltive = 0;
int max = 0;
int maxIndex = 0;
//one pass - find the max index that produces max sub array
for(int i = 0; i< arr.length; i ++)
{
cummaltive = cummaltive+arr[i];
if(cummaltive > max)
{
max = cummaltive;
maxIndex = i;
}
}
//second pass loop till max pointer
for(int i = 0; i<=maxIndex; i ++)
{
System.out.println(arr[i]);
}
}
```

C++ function:

```
{
int * maxSequence(int * arr, int length)
{
int max = 0, start = 0, end = 0, actual_start = 0, sum = 0;
for(int i = 0; i < length; i++)
{
sum += arr[i];
if(sum < 0)
{
sum = 0;
start = i + 1;
}
else if(sum > max)
{
max = sum;
end = i;
actual_start = start;
}
}
int extension = end - actual_start + 1;
int * result = new int[extension];
for(int i = 0; i < (extension); i++)
result[i] = arr[i + actual_start];
return result;
}
```

}

This can be solved in single pass through the array .. It is called Kandane's Algorithm

- nsaichand April 26, 2014