Skip to content

2407. Longest Increasing Subsequence II 👍

  • Time: $O(n\log 10^5)$
  • Space: $O(10^5)$
 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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
struct SegmentTreeNode {
  int lo;
  int hi;
  int maxLength;
  std::unique_ptr<SegmentTreeNode> left;
  std::unique_ptr<SegmentTreeNode> right;
  // maxLength := the maximum length of LIS ending in [lo..hi]
  SegmentTreeNode(int lo, int hi, int maxLength,
                  std::unique_ptr<SegmentTreeNode> left = nullptr,
                  std::unique_ptr<SegmentTreeNode> right = nullptr)
      : lo(lo),
        hi(hi),
        maxLength(maxLength),
        left(std::move(left)),
        right(std::move(right)) {}
};

class SegmentTree {
 public:
  explicit SegmentTree() : root(make_unique<SegmentTreeNode>(0, 1e5 + 1, 0)) {}

  void updateRange(int i, int j, int maxLength) {
    update(root, i, j, maxLength);
  }

  // Returns the maximum length of LIS ending in [i..j].
  int queryRange(int i, int j) {
    return query(root, i, j);
  }

 private:
  std::unique_ptr<SegmentTreeNode> root;

  void update(std::unique_ptr<SegmentTreeNode>& root, int i, int j,
              int maxLength) {
    if (root->lo == i && root->hi == j) {
      root->maxLength = maxLength;
      root->left = nullptr;
      root->right = nullptr;
      return;
    }
    const int mid = root->lo + (root->hi - root->lo) / 2;
    if (root->left == nullptr) {
      root->left = make_unique<SegmentTreeNode>(root->lo, mid, root->maxLength);
      root->right =
          make_unique<SegmentTreeNode>(mid + 1, root->hi, root->maxLength);
    }
    if (j <= mid)
      update(root->left, i, j, maxLength);
    else if (i > mid)
      update(root->right, i, j, maxLength);
    else {
      update(root->left, i, mid, maxLength);
      update(root->right, mid + 1, j, maxLength);
    }
    root->maxLength = merge(root->left->maxLength, root->right->maxLength);
  }

  int query(std::unique_ptr<SegmentTreeNode>& root, int i, int j) {
    if (root->left == nullptr)
      return root->maxLength;
    if (root->lo == i && root->hi == j)
      return root->maxLength;
    const int mid = root->lo + (root->hi - root->lo) / 2;
    if (j <= mid)
      return query(root->left, i, j);
    if (i > mid)
      return query(root->right, i, j);
    return merge(query(root->left, i, mid), query(root->right, mid + 1, j));
  }

  int merge(int left, int right) const {
    return max(left, right);
  };
};

class Solution {
 public:
  int lengthOfLIS(vector<int>& nums, int k) {
    int ans = 1;
    SegmentTree tree;

    for (const int num : nums) {
      const int left = max(1, num - k);
      const int right = num - 1;
      // the maximum length of LIS ending in [left..right] + the current number
      const int maxLength = tree.queryRange(left, right) + 1;
      ans = max(ans, maxLength);
      tree.updateRange(num, num, maxLength);
    }

    return ans;
  }
};