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
|
|
