Amazon Interview Question
Software Engineer / Developersint max_subarray(int* array, int size)
{
int max_ending = 0, max_so_far = 0, i = 0;
int start = 0, end = 0, curr_start = 0, curr_end = 0;
if (array == NULL)
return -1;
while (i < size) {
if (max_ending > 0) {
max_ending = max_ending + array[i];
curr_end = i;
} else {
max_ending = array[i];
curr_start = curr_end = i;
}
if (max_so_far < max_ending) {
max_so_far = max_ending;
start = curr_start;
end = curr_end;
}
i++;
}
printf("Start = array[%d]=%d and End = array[%d]=%d \n", start,
array[start], end, array[end]);
printf("Start = %d and End = %d \n", start, end);
return max_so_far;
}
int main(void)
{
int my_array[] = {-2, 4, -4, -6, 6, -1, 5, -3, 5, -8};
printf("Max subarray = %d \n",
max_subarray(my_array, 10));
return 0;
}
int findMaxContSum(){
max = numbers[0];
sum = numbers[0];
for(int i=1; i<n; i++){
sum = sum + numbers[i];
if( sum > max ) {
max = sum;
}
else if (sum<0) {
sum=0;
}
}
}
- sachin323 March 28, 2010