- #1

leon1127

- 486

- 0

## Homework Statement

Given an array with random real elements, find the indices pair (i, j) where j>i s.t

a[j] - a

*is maximised in O(n ln n) time*

I tried sorting the array of (value, index) pair with O(n ln n) sort, and then inspect the index array. However it does not suggest me any fast alsogorithm to find the (i, j) pair fast from here.

O(n ln n) suggest that recursion is necessary. However the difference a[j] - a

I tried sorting the array of (value, index) pair with O(n ln n) sort, and then inspect the index array. However it does not suggest me any fast alsogorithm to find the (i, j) pair fast from here.

O(n ln n) suggest that recursion is necessary. However the difference a[j] - a

*depends on all the permutation of pairs, I do not see an obvious way to divide the problem space. Any suggestion is appriciated.*