本文共 643 字，大约阅读时间需要 2 分钟。
Given an array A[], find (i, j) such that A[i] < A[j] and (j - i) is maximum.
--------------------------------------------------------------
A Typical two-direction search...
MaxDiff(vector arr){ if(arr.size()==0) return 0; int n=arr.size(),i,j; vector Lmin(n,0); vector Rmax(n,0); Lmin[0]=arr[0]; for(i=1;i =0;i--) Rmax[i]=max(arr[i],Rmax[i+1]); int maxdiff=0; i=0,j=0; while(i O(n) time and O(n) space solution. Tested! The key observation is the two auxiliary arrays LMin and RMax which saves the smallest value left of i and biggest value right of i 转载地址：http://mzboi.baihongyu.com/