可能重复:
在排列中查找已排序的子序列
给定一个数组A,其中包含1,2,...,n的排列.如果A [i..j]
中出现的所有数字
都是连续数字(可能不是有序),则数组A的子块A [i..j] 被称为有效块.
给定阵列A = [7 3 4 1 2 6 5 8],有效块为[3 4],[1,2],[6,5],
[3 4 1 2],[3 4 1 2 6 5 ],[7 3 4 1 2 6 5],[7 3 4 1 2 6 5 8]
所以上面排列的计数是7.
给出O(n log n)算法来计算有效块的数量.