1.3.2 Longest Increasing Subsequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

/*

Given an array of elements, determine a longest subsequence where all elements are in strictly
increasing order. The subsequence is not necessarily contiguous or unique, so only one such answer
will be found. The answer is computed by scanning left to right while maintaining, for each length,
the smallest possible tail value of an increasing subsequence of that length. Each element extends
or improves one of these tails, located in O(log n) by binary search; predecessor links then
reconstruct the subsequence. The comparator `comp` defines the ordering and defaults to
`std::less<>`.

- `longest_increasing_subsequence(a, comp = std::less<>())` returns the indices of one longest
  strictly increasing subsequence of `a` according to `comp`, in order.

Time Complexity:
- O(n log n) per call, where $n$ is the size of `a`.

Space Complexity:
- O(n) auxiliary and O(n) for the returned indices.

*/

#include <algorithm>
#include <functional>
#include <vector>

template<typename T, typename Compare = std::less<>>
std::vector<int> longest_increasing_subsequence(const std::vector<T> &a, Compare comp = Compare{}) {
  int n = static_cast<int>(a.size());
  if (n == 0) {
    return {};
  }
  int len = 0;
  // prev[i] = index of the predecessor of element i in its LIS (or -1 for the first LIS element).
  // tail[i] = index of the last element of the best known LIS of length i + 1.
  std::vector<int> prev(n), tail(n);
  for (int i = 0; i < n; i++) {
    // Find the tail to extend or improve. Comparing by value through the stored indices keeps tail
    // index-based for reconstruction. Switch to an upper-bound search for a non-decreasing result.
    int pos = static_cast<int>(
        std::lower_bound(
            tail.begin(), tail.begin() + len, i, [&](int t, int x) { return comp(a[t], a[x]); }
        ) -
        tail.begin()
    );
    if (pos == len) {
      len++;
    }
    prev[i] = pos > 0 ? tail[pos - 1] : -1;
    tail[pos] = i;
  }
  // Optional: reconstruct one longest increasing subsequence.
  std::vector<int> res(len);
  for (int i = tail[len - 1]; i != -1; i = prev[i]) {
    res[--len] = i;
  }
  return res;
}

/*** Example Usage ***/

#include <cassert>
using namespace std;

int main() {
  vector<int> a{-2, -5, 1, 9, 10, 8, 11, 10, 13, 11};
  assert((longest_increasing_subsequence(a) == vector<int>{1, 2, 3, 4, 6, 8}));

  vector<int> b{1, 4, 3, 2};
  assert((longest_increasing_subsequence(b, greater<int>()) == vector<int>{1, 2, 3}));
  return 0;
}