# Hints: Useless for LIS

Define `dp_end[i]`

to be the length of the longest increasing subsequence that ends at index `i`

.

Similarly, define `dp_start[i]`

to be the length of the longest increasing subsequence that starts at index `i`

.

Come up with an `O(n^2)`

algorithm to populate both the DP arrays.

The answer for the `i-th`

element depends only on 2 values, `dp_start[i]`

and `dp_end[i]`

. Can you come up with the expression?

Think of the `i-th`

element as the partition point of the subsequence. Will you take optimal decisions on both sides of the parition point?

If `i-th`

element is a partition point, then we can combine the best LIS ending at `i`

and best LIS starting at `i`

to get LIS of the entire array. However, `i-th`

element is double counted. Therefore, the expression is

```
dp_start[i] + dp_end[i] - 1 == LIS
```

If this equation is satisfied, the `i-th`

element is part of at least one LIS of the original array.

This is the same trick that we use in **Dijkstra’s algorithm** to figure out which edges lie on at least one shortest path. I recently created a practice problem on this in my Codeforces group. You can check it out here

The novelty of the problem ends here. However, the current solution is `O(n^2)`

, but optimizing it to `O(n log(n))`

is as standard as it gets.

We will use 2 tricks

Use **coordinate compression** to reduce numbers to the range `1...n`

. This is fairly standard in problems where only the rank matters.

```
void compress(vector<int> &a) {
int n = a.size();
map<int, int> rank;
for (int i = 0; i < n; i++) {
rank[a[i]] = 1;
}
int now = 1;
for (auto &kv : rank) {
rank[kv.first] = now++;
}
for (int i = 0; i < n; i++) {
a[i] = rank[a[i]];
}
}
```

The `dp_start`

and `dp_end`

array that we computed in **Hint 1** can actually be computed in `O(n log(n))`

. In fact, the CP algorithm page for LIS tells you exactly how to do that.

If you scroll towards the end, they define an auxillary array `t`

where

```
t[a[i]] = dp[i]
```

With this `t`

array, DP computation is as simple as querying prefix or suffix maxima. You can use Atcoder’s segtree library for the same.