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.