Help for an algorithm, Thanks - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Computation - 科学计算

Help for an algorithm, Thanks

Help for an algorithm, Thanks# Computation - 科学计算

r*e2003-09-05 07:09

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*e2003-09-05 07:09

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;iif (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