r****e 发帖数: 9 | 1 Given an array A with positive numbers, find an efficient algorithm to find
out the Maximum of A[j]-A[i], j>i.
My solution is: Divide the array into two parts, first half and second half.
Then the location of j and i have three possibles. 1) j,i are in the first
half. 2) j, i are in the second half. 3) i is in the first and j in sencond.
For 1) and 2), I can use recursive to find out. For 3) I need to find out the
minimum element in the first half and the maximum element in the second half.
Then | m****e 发帖数: 7 | 2 Here's an O(n) one: (Given array A[0..(n-1)])
int x=A[0],y=A[1]-x;
for (int i=1;i
if (x>A[i]) x=A[i];
if (y
}
return y;
【在 r****e 的大作中提到】 : Given an array A with positive numbers, find an efficient algorithm to find : out the Maximum of A[j]-A[i], j>i. : My solution is: Divide the array into two parts, first half and second half. : Then the location of j and i have three possibles. 1) j,i are in the first : half. 2) j, i are in the second half. 3) i is in the first and j in sencond. : For 1) and 2), I can use recursive to find out. For 3) I need to find out the : minimum element in the first half and the maximum element in the second half. : Then
|
|