## Ebay Interview Question

Software Engineer / Developers**Team:**Traffic

**Country:**United States

**Interview Type:**In-Person

I'm not sure if this answer is correct. The question is about subsequence not subarray. In case of the input: {1, -10, 2, -10, 3} the output should be 6 not 3.

I assumed that its about max sub array which sometimes is also called as maxsubsequence. An e.g. with the question would have been better.

public int maxSubArray(int[] A) {

if(A.length == 0) return 0;

if(A.length == 1) return A[0];

int[] sums = new int[A.length];

sums[0] = A[0];

for(int i=1; i < A.length; i++){

sums[i] = sums[i-1]>0?sums[i-1] + A[i]:A[i];

}

int max = A[0];

for(int i=0; i < sums.length; i++){

if(max < sums[i]) max = sums[i];

}

return max;

}

package ms.ArraysStrings;

public class MaxSubArraySum {

public int findMaxSum(int[] inputArray) {

int currentMax = 0, maxSum = 0;

int curStart = 0, curEnd = 0;

int start=0, end=0;

for (int i = 0; i < inputArray.length; i++) {

if (inputArray[i] > currentMax + inputArray[i]) {

currentMax = inputArray[i];

curStart = i;

curStart = i;

} else {

currentMax = currentMax + inputArray[i];

curEnd = i;

}

if (currentMax > maxSum) {

maxSum = currentMax;

start = curStart;

end = curEnd;

}

}

System.out.println("Start of Max "+start+ " "+"End of Max "+end);

return maxSum;

}

public static void main(String[] args) {

int[] inputArray = { -2, -3, 4, -1, -2, 1, 5, -3 };

MaxSubArraySum mSum = new MaxSubArraySum();

int output = mSum.findMaxSum(inputArray);

System.out.println("Maximum sub array sum " + output);

}

}

github.com/techpanja/interviewproblems/tree/master/src/arrays/maxsubarray

- techpanja January 08, 2014