こちらの記事ではスタック構造体を使った単調スタックの説明を行った。
これとは別に配列を使った単調スタックの実装があるので解説を行う。
配列を使うメリットとしてはソート済みの配列になるので配列に対して二分探索が可能となる。
これを使ってLIS問題を実装する。

考え方

LISというのはある配列Aからいくつかの要素を排除することで得られる部分配列の中で、単調増加になっているものの最大配列サイズを見つける問題。

例えば下記配列Aがあるとする

A[] = {1 2 5 4 10 3}

考え方としては、配列Sを作成し下記のように定義する。

S[i] = 配列Aから長さiの部分列を作成したときの最後の要素

S[i]は小さければ小さいほど、後に選択できる要素の可能性が大きくなるので貪欲に小さい数を選ぶことで配列Sを作成できる。
配列Aから順番に要素を取り出し、配列Sのどこに当てはまるかを二分探索を使って探していく。

S[] = {1 2 3 10}

注意が必要なのは作成した配列Sは実際のLIS配列ではないということ。
あくまで長さiの部分配列の最終要素の配列である。
上記の例では配列Aで3は10の前にあるのでこの部分配列は作成できない。

実装

int lengthOfLIS(vector<int>& nums) {
    vector<int> stack;
    for (int i: nums) {
        if (stack.empty() || i > stack.back()) stack.push_back(i);
        else *lower_bound(stack.begin(), stack.end(), i) = i;
    }
        
    return stack.size();
}

関連問題

300. Longest Increasing Subsequence

2111. Minimum Operations to Make the Array K-Increasing