# Distance Maximizing Problem

11 Dec 2011

```Given an array A of integers, find the maximum of j-i subjected to the constraint of A[i] < A[j]. ```

This is a really really good interview question. I love this kind of questions.

It is simple and bears different solutions. Following a good practice, the simplistic solution should be laid down first.

We can just do a brute-force solution, iterating through every pair and get the maximum. That is O(n^2) in time.

In order to get a better solution, we need more insights.

### Observation 1

It's all about random exploration, right?

Let's say we have:

```a[0] a[1] a[2] a[3] ... a[n-1] ```

Since we want to find the maximum of `j-1`. It makes sens to start with 2 pointers at `a[0]` and `a[n-1]`. If `a[0]` < `a[n-1]`, we get the solution immediately. If it is not, what do we do?

We got nothing.

I cannot come up with any observation. Oh god.

Ok, let's have a look at Leetcode.com.

## Leetcode.com's super cool solution

Let's say we have:

```10 5 9 4 3 1 6 8 2 ```

If we have the solution already, 6 will never be a part of the answer. This is because it is always better to choose 1 rather than 6. (1 is more on the left and is lesser.)

Now it's obvious that the only possible starting points are 5, 4, 3, and 1.

This is a crucial observation. We can devise an `O(n)` solution from it. I'll leave it as an exercise for future Tanin.

## Lesson Learned

One way to find useful observations is to consider all possible solutions and rule out some combinations.