本文首发为CSDN博客，地址为：http://blog.csdn.net/xxzhangx/article/details/53505867
欢迎关注，谢谢！引用转载请注明作者和地址！
题目 : 给定一个整型数组，找出最大的下标距离j-i，当且仅当A[i]<A[j]和i<j。
伪代码
int maxIndexDistance(int A[]){
if (A==null || A.length<2) return 0;
boolean inDescSeq[] = new boolean[A.length];
int min = A[0],n=A.length;
inDescSeq [0] = true;
for(int i = 1;i <n;i++){
if(A[i] < min){
//做下降序列的标记
inDescSeq[i] = true;
min = A[i];
}
}
int maxDist = 0,i=n-1,j=n-1;
while(i>=0){
if (inDescSeq[i] == false){
i--; //倒序找出下一个降序列的元素
continue;
}
while ((A[j] <= A[i]) && (j>i))
j --; //从后往前移动直至找到符合的元素
if((j-i) > maxDist){
maxDist = j-i;
}
i--;
}
return (maxDist);
}
R语言
maxIndexDistance<-function(a)
{
if (is.null(a) || length(a) < 2)
{
return (0)
}
inDescSeq = rep('FALSE',length(a))
min = a[1];n=length(a)
inDescSeq[1] = 'TRUE'
for(i in 2:length(a))
{
if(a[i] < min)
{
inDescSeq[i] = 'TRUE'
min = a[i]
}
}
maxDist =0;i = n;j=n;
while(i >= 1)
{
if(inDescSeq[i] == 'FALSE')
{
i = i -1;
}
while ((a[j] <= a[i]) && (j > i))
{
j = j-1
}
if ((j-i) > maxDist)
{
maxDist = j-i
}
i = i -1
}
return(maxDist)
}
#1
> a<-c(1:20,30:14,2:23,54:33)
> maxIndexDistance(a)
[1] 59
#2
> a<-c(5,3,4,0,1,4,1)
> maxIndexDistance(a)
[1] 4
