第一種方法：
用兩重循環(huán)對(duì)每對(duì)點(diǎn)都試一下颜屠，然后取最大值即可，時(shí)間復(fù)雜度為O(n2)
#include?
#include
usingnamespacestd;
intmaxIndexDiff(inta[],intn)
{
intmaxDiff = -1;
for(inti =0; i <? n; ++i)
{
for(intj =n-1; j > i ; --j)
{
if(a[j]>a[i]) maxDiff = max(maxDiff,j-i);
}
}returnmaxDiff;
}
int
main()
{
inta[]={9,2,3,4,5,6,7,8,18,0};
intn =sizeof(a)/sizeof(a[0]);
intmaxDiff =maxIndexDiff(a,n);
cout<
}
第二種方法:
首先對(duì)數(shù)組按照高度排序從小到大排序更啄，如果高度相等的話纳令，按照索引從小到大排序柠贤。
此時(shí)只需要在右邊找一個(gè)索引值j帮孔，在左邊找一個(gè)索引值i雷滋，使j-i最大即可。
可以建立一個(gè)rightMax數(shù)組，記錄下每個(gè)索引右邊的最大值晤斩，注意從右邊往左邊掃描焕檬，計(jì)算右邊最大值簡(jiǎn)單些。
然后將當(dāng)前的rightMax與排序后原始索引作差取最大值即可澳泵。時(shí)間復(fù)雜度O(nlogn)
#include #include#includeusingnamespacestd;structnode{intindex;intheight;
node(intidx =0,inth =0):index(idx),height(h){}booloperator<(constnode& a)const{if(height!=a.height)returnheight
}
};intmaxIndexDiff(inta[],intn){
vectorb(n);for(inti =0; i < n ; ++ i) {b[i].index = i;b[i].height =a[i];}
sort(b.begin(),b.end());
vector rightMax(n,b[n-1].index);
rightMax[n-1]=b[n-1].index;for(inti = n -2; i>=0; --i){if(b[i].index > rightMax[i+1]) rightMax[i] =b[i].index;elserightMax[i]=rightMax[i+1];
}intmaxDiff = -1;for(inti =0; i< n ; ++i){
maxDiff= max(maxDiff,rightMax[i]-b[i].index);
}returnmaxDiff;
}intmain(){inta[]={9,2,3,4,5,6,7,8,18,0};intn =sizeof(a)/sizeof(a[0]);intmaxDiff =maxIndexDiff(a,n);
cout<
}
還有一種方法是利用二分查找揩页，注意j-i的值必定在0~n-1之間（索引是從0開(kāi)始的）
取中間一個(gè)值mid=(0+n-1)/2，
如果存在a[i+mid]>a[i]烹俗，則必然j-i至少是mid，繼續(xù)向上二分查找
否則萍程，j-i不超過(guò)mid幢妄，則向下二分查找
#include #include#includeusingnamespacestd;boolexist(inta[],intn,intk){for(inti =0; i+k< n; ++i){if(a[i] < a[i+k])returntrue;
}returnfalse;
}intmaxIndexDiff(inta[],intn){intleft =0, right = n-1;while(left <=right){intmid = (left+right)/2;if(exist(a,n,mid)) left=mid+1;elseright = mid-1;
}returnright;
}intmain(){inta[]={9,2,3,4,5,6,7,8,18,0};intn =sizeof(a)/sizeof(a[0]);intmaxDiff =maxIndexDiff(a,n);
cout<
}
第三種方法：
從左向右掃描一遍，記錄每個(gè)索引左邊的最小值（包括自己）茫负，leftMin[0..n-1]
從右向左掃描一遍蕉鸳，記錄每個(gè)索引右邊的最大值（包括自己），rightMax[0..n-1]
要注意的是：
對(duì)于leftMin[i]忍法，其左邊的leftMin[0..i-1]都大于等于leftMin[i]潮尝，其右邊的left[i+1..n-1]都小于leftMin[i]
對(duì)于rightMax[j]，其左邊的rightMax[0..j-1]都大于等于rightMax[j]饿序，其右邊的rightMax[j+1..n-1]都小于rightMax[j]
對(duì)于leftMin[i] 和rightMax[j]
如果leftMin[i]leftMin勉失，記錄當(dāng)前的j-i，使++j
否則leftMin[i]>=rightMax[j], 則i的左邊肯定都比rightMax[j]大原探，要增大++i乱凿，
#include #include#include#includeusingnamespacestd;intmaxIndexDiff(inta[],intn){
vector leftMin(n,a[0]),rightMax(n,a[n-1]);for(inti =1; i < n; ++i ) leftMin[i] = min(a[i],leftMin[i-1]);for(inti = n-2; i>=0; -- i) rightMax[i] = max(a[i],rightMax[i+1]);inti =0, j=0, maxDiff = -1;while(i
maxDiff= max(maxDiff,j-i);
j++;
}else++i;
}returnmaxDiff;
}intmain(){inta[]={9,2,3,4,5,6,7,8,18,0};intn =sizeof(a)/sizeof(a[0]);intmaxDiff =maxIndexDiff(a,n);
cout<
}
第一種方法：
從左往右求下標(biāo)0到 k - 1 的最小值MIN
從右往左求 下標(biāo)k到n -1 的最大值MAX
對(duì)于每個(gè)k都有一個(gè)MAX - MIN的值徒蟆，最后求這個(gè)值的最大值即可。
例如數(shù)組：4 5 2 6 3 1
K：1 2 3 4 5
MIN：?4 4 2 2 2
MAX：6?6 6?3 1
MAX - MIN型型，最大的值為6 - 2 = 4段审， 即為結(jié)果
第二種方法：
令b[j] = a[j + 1] - a[j]，
那么a[j] - a[i]=(a[i+1]-a[i])+(a[i+2]-a[i+1])+...+(a[j]-a[i-1])
= b[i] +b[i+1]+ ...+ b[j - 1]闹蒜，
即將問(wèn)題轉(zhuǎn)化成求一個(gè)數(shù)組子序列的最大值寺枉。這個(gè)過(guò)程的算法是有O(n)的算法的。
