百度程序开发面试题
任给一个包含10个元素的数组A ，在只能遍历数组一遍
的情况下，寻找A[j]-A[i]差值的最值(注：j>i)
主要思想
本来准备每次选取局部最优解，以获得全局的最优解，
后来发现这样会有一些遗漏。例如，求解数组
A[5]={1,10,-10,100,0},遍历数组的时候局部最优是
A[3]-A[0]=99，然而真正的解应该是A[3]-A[2]=110。因为算法
简单的跳过了-10，没有将其保存，也就错过了最优解。
事实上，在以上的方法中加入一个变量t ，用它来记录
A[2]--A[K]之间的最小元素就可以防止遗漏最优解。变量K
是当前遍历到的数组下标。
局部最优：T1=A[j]-A[i]
T2=A[K]-A[i]
T3=A[K]-A[j]
根据题意，当前下标K>j>i，所以可能的情况就是以上3种，
我们需要找出其中的最值作为局部最优解。
无遗漏解：A[K]-A[t]
可以想象，如果局部解不是最优的话，那一定是存在一个元
素A[t]比A[j]和A[i]更小，那么A[K]-A[t]就是那个解。
#include
#define para 10
void main()
{
int i,j,k,t; //i,j存放最优解下标，k 为数组遍历下标， t 为a[2]到a[k-1]之间最小值下标
int tmp1,tmp2,tmp3,tmp4; int a[para]; printf("输入待筛选数组%d个元素\n",para); for(k=0;k
if(a[t]>a[k]) //寻找a[2]a[k-1]间最小值，以防遗漏
{
t=k;
}
if(tmp1
{
if(tmp2
{
i=j;
j=k;
}
else
{
j=k;
}
}
else
{
if(tmp1
{
i=j;
j=k; //a[k]-a[j]符合条件 //a[k]-a[i]符合条件 //a[k]-a[j]符合条件
} } if(t
}
} printf("result: j=%d,i=%d\n",j,i); printf("输出最大差值:a[%d]-a[%d]=%2d\n",j,i,a[j]-a[i]); { } tmp4=a[k]-a[t]; if(tmp4>a[j]-a[i]) //a[k]-a[t]符合条件 { } j=k; i=t;
运行效果
图 1
图 2