Widest Inversion | Algorithms Notes

Widest Inversion | Algorithms Notes

Given an array A of n integers, find the maximum of R – L where A[L] > A[R] in time O(n).

Solution:

For an index i, if there exists k < i but A[k] > A[i], then i cannot be the candidate of L. Similarly, for an index j, if there exists k > j but A[k] < A[j], then j cannot be the candidate of R. By using these two properties, we can construct two candidate sets for L and R, where L = { i : A[i] is the maximum in A[1..i] } and R = { j : A[j] is the minimum in A[j..n] }. Note that if we list the elements in A correspond to the indices in L or R, the elements are increasing in the index. For each i in L, we want to find the best partner P(i) in R, such that A[i] > A[P(j)] and P(j) – i is maximized. P(i) is the maximum j in R with A[j] < A[i]. Since P(i) is increasing in i, all partners can be found in linear time.

解法：

對一索引i而言，如果存在k < i且A[k] > A[i]，那i就不可能會是L的候選。同理，對一索引j而言如果存在有k > j且A[k] < A[j]，那j就不可能是R的候選。利用此性質，我們可以建構兩個候選集合，L = {i : A[i]是A[1..i]中最大值}以及R = {j : A[j]是A[j..n]中最小值}。如果我們把L或R當做索引集合，列出A中相應的元素，這些元素會是按照索引值遞增的。 對於每一個在L中的索引i，我們想要找出其在R中最佳夥伴P(i)使得A[i] > A[P(j)]且P(j) – i最大化。P(i)即為R中最大的j使得A[j] < A[i]。因為P(i)是對於i遞增的，所有P(i)的值可在線性時間內找到。

David Ginat, "Algorithmic Problem Solving and Novel Associations," Olympiads in Informatics 5 (2011), 3-11

Read full article from Widest Inversion | Algorithms Notes