在待字闺中看到陈利人老师发的这个题，自己写了一下。题目是： > 给定无序数组A，在线性时间内找到i 和 j， j > i,并且保证A[j] - A[i]是最大的。
这个问题比较简单，看到后第一反应是最大连续和子数组问题的变种，算出每相邻两个数之间的差值，然后寻找最大连续和子数组，下面是代码。
#include<iostream>
#include<climits>
using namespace std;
void print(int *array, int len){
if(array == NULL || len <= 0)
return;
int i;
for(i = 0; i < len; i++)
cout << array[i] << " ";
cout << endl;
}
void findTheTwoNum(int *array, int len, int& start, int& end){
if(array == NULL || len <= 0)
return;
int i = 0;
int max = 0, maxsofar = 0;
for(i = 1; i < len; i++){
if(maxsofar + array[i] - array[i-1] > 0)
maxsofar += array[i] - array[i-1];
else{
maxsofar = 0;
start = i;
}
if(maxsofar > max){
max = maxsofar;
end = i;
}
}
}
void findTheTwoNumV2(int *array, int len, int& start, int& end){
if(array == NULL || len <= 0)
return;
int max = 0,min = INT_MIN;
int i;
for(i = 0; i < len; i++){
if(array[i] < min){
min = array[i];
start = i;
}else{
if(array[i] - min > max){
max = array[i] - min;
end = i;
}
}
}
}
int main(){
int array[] = {3,7,8,5,9,2,10};
//int array[] = {3,7,8,5,1,2,10};
int len = sizeof(array) / sizeof(int);
int start = 0,end = 0;
print(array,len);
findTheTwoNum(array,len,start,end);
cout << "start:array[" << start << "] = " << array[start] << endl;
cout << "end: array[" << end << "] = " << array[end] << endl;
return 0;
}
后面看到网友的回复，还有更加简单的思路，遍历一遍，保持A[0]-A[j-1]中最小的数min,计算A[j] - min，更新最大差值，代码在上面给出了。