Adobe : Given an array A[i..j] find out maximum j-i such that A[i]<a[j]

Given an array A[i..j] find out maximum j-i such that A[i]<a[j] in
O(n) time.

PS . 是前面一个柱状统计图最大矩形面积的一个子问题

一点都看不懂呢   郁闷啊

哈，发现那个Discuz! Board太神奇了！！！

两个算法：
（1）O(NlogN)的算法：
定义一个辅助数组B[], B[i]保存A[0...i]内的最小值，B[]是非递增序列，则：
对于A[k]，在B[0...k-1]中二分查找小于A[k]的最大值B[s]，maxValue=max{maxValue, k-s}
(2)O(N)的算法：
定义两个辅助数组LMin[]和RMax[], LMin[i]保存A[0...i]内的最小值， RMax[j]保存A[j...n-1]内的最大值，
刚开始两个指针i，j分别指向LMin[]和RMax[]开始，
若：LMin[i]<RMax[j], 则：j++
若：LMin[i]>=RMax[j], 则：i++
这个过程中j-i最大值即为所求。
这个比较容易证明：
LMin[]:对于A[i]<A[j]且i<j,则对于某个A[k],(k>j>i)，则k-i>k-j,此时只计算k-i即可，也就是保存A[0...j]的最小值。

这个问题是是前面一个柱状统计图最大矩形面积的一个子问题？ 没看出来，楼主能解释一下吗？