#
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.