aboutsummaryrefslogtreecommitdiff
path: root/num_longest_incr_subseq.cpp
blob: bf6529b9cbdf92a27863b8368103d39ac90969a9 (plain)
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
// 673. Number of Longest Increasing Subsequence
#include "leetcode.h"

/*
 * given an integer array 'nums', return the number of longest increasing
 * subsequences. notice that the sequence has to strictly increasing.
 */

class Solution {
public:
  int findNumberOfLIS(vector<int> &nums) {
    if (nums.empty())
      return 0;
    vector<vector<pair<int, int>>> dyn(nums.size() + 1);
    int curr_max = 0;
    for (int i = 0; i < nums.size(); ++i) {
      int l = 0, r = curr_max;
      while (l < r) {
        int mid = l + (r - l) / 2;
        if (dyn[mid].back().first < nums[i])
          l = mid + 1;
        else
          r = mid;
      }
      int options = 1, row = l - 1;
      if (row >= 0) {
        int l1 = 0, r1 = dyn[row].size();
        while (l1 < r1) {
          int mid = l1 + (r1 - l1) / 2;
          if (dyn[row][mid].first < nums[i])
            r1 = mid;
          else
            l1 = mid + 1;
        }
        options = dyn[row].back().second;
        options -= !l1 ? 0 : dyn[row][l1 - 1].second;
      }
      dyn[l].push_back(
          {nums[i],
           (dyn[l].empty() ? options : dyn[l].back().second + options)});
      if (l == curr_max)
        curr_max++;
    }
    return dyn[curr_max - 1].back().second;
  }
};

int main() {
  Solution obj;
  vector<int> n1 = {1, 3, 5, 4, 7}, n2 = {2, 2, 2, 2, 2};
  printf("%d\n", obj.findNumberOfLIS(n1)); // expect: 2
  printf("%d\n", obj.findNumberOfLIS(n2)); // expect: 5
}