一、题目描述
给定一个整型数组，找出最大下标距离
二、直观方案（时间复杂度为O(n^2)）
对每个元素，从其后找出比其大的元素，并计算下标距离，取距离中的最大值即可。该
方案的时间复杂度为O(n^2)。那么能不能优化下呢？
三、优化方案（时间复杂度为O(n)）
存在这样一个事实，当
基于以上的事实，我们只要从数组的第一个元素开始，找一个下降的序列，从尾部开始扫描，求出最大下标距离。
例如，数组
第一步，，
第二步，
第三步，
第四步，
第五步，
第六步，
第七步，
第八步，
第九步，i=-1，结束；
代码实现如下：
//返回数组中最大下标距离j-i,当且仅当nArray[i]<nArray[j],j>iint MaxSubDistance( int nArray[], int nCount ){//查找一个下降序列bool* bDescSeq = new bool[nCount];memset( bDescSeq, 0, sizeof(bool)*nCount );int nMinNum = nArray[0];for ( int i = 1; i < nCount; ++i ){if ( nArray[i] < nMinNum ){bDescSeq[i] = true;nMinNum = nArray[i];}}int nMaxSubDistance = 0;int i = nCount – 1;int j = nCount – 1;while( i >= 0 ){if( !bDescSeq[i] ){–i;continue;}while( j > i && nArray[i] >= nArray[j] )–j;if ( (j – i) > nMaxSubDistance ){nMaxSubDistance = j – i;//j = nCount – 1;//这句多余，这句加上的话，时间复杂度则为O(n^2)了。}–i;}if ( NULL != bDescSeq ){delete[] bDescSeq;bDescSeq = NULL;}return nMaxSubDistance;}
系列文章说明:1.本系列文章[算法练习],仅仅是本人学习过程的一个记录以及自我激励,没有什么说教的意思。如果能给读者带来些许知识及感悟，那是我的荣幸。2.本系列文章是本人学习陈东锋老师《进军硅谷，程序员面试揭秘》一书而写的一些心得体会，文章大多数观点均来自此书，特此说明！3.文章之中,难免有诸多的错误与不足,欢迎读者批评指正,谢谢.
作者：山丘儿
出门走好路，出口说好话，出手做好事。
