Amazon Interview Question
Find the subarray with the largest sum given an unsorted array of positive and negative numbers.
Interview Answer
Anonymous
Mar 13, 2014
void maxSumSubArray( int *array, int len, int *start, int *end, int *maxSum ) { int maxSumSoFar = -2147483648; int curSum = 0; int a = b = s = i = 0; for( i = 0; i maxSumSoFar ) { maxSumSoFar = curSum; a = s; b = i; } if( curSum < 0 ) { curSum = 0; s = i + 1; } } *start = a; *end = b; *maxSum = maxSumSoFar; }