673. Number of Longest Increasing Subsequence

01//DP
02//Runtime: 72 ms, faster than 51.00% of C++ online submissions for Number of Longest Increasing Subsequence.
03//Memory Usage: 13 MB, less than 11.11% of C++ online submissions for Number of Longest Increasing Subsequence.
04//time: O(N^2), space: O(N)
05class Solution {
06public:
07    int findNumberOfLIS(vector<int>& nums) {
08        int n = nums.size();
09        if(n <= 1) return n;
10        vector<int> lengths(n, 0);
11        vector<int> counts(n, 1);
12        
13        int maxlen = 0;
14        int ans = 0;
15        
16        for(int j = 0; j < n; j++){
17            for(int i = 0; i < j; i++){
18                //[0...i] and [0...j] which j > i
19                if(nums[i] < nums[j]){
20                    if(lengths[i] >= lengths[j]){
21                        /*
22                        lengths[i] + 1 > lengths[j]
23                        so we discard the previously found LIS ending at nums[j],
24                        instead just use what extends from LIS ending at nums[i]
25                        */
26                        lengths[j] = lengths[i] + 1;
27                        //LIS ending at j is extending from LIS ending at i
28                        counts[j] = counts[i];
29                    }else if(lengths[i] + 1 == lengths[j]){
30                        /*
31                        [0...j] can be generated by [0...i] plus nums[j]
32                        the previous found LIS ending at j are reserved
33                        */
34                        counts[j] += counts[i];
35                    }
36                }
37            }
38            
39            if(maxlen < lengths[j]){
40                /*
41                current found LIS's length is the longest,
42                so overwrite the info about what we previous found
43                */
44                maxlen = lengths[j];
45                ans = counts[j];
46            }else if(maxlen == lengths[j]){
47                //accumulate the count of LIS with length equal to maxlen
48                ans += counts[j];
49            }
50        }
51        
52        return ans;
53    }
54};
55
56//
57class NodeValue{
58public:
59    int length;
60    int count;
61    NodeValue(int l, int c) : length(l), count(c) {}
62};
63
64class Node{
65public:
66    int range_left, range_right;
67    Node *left, *right;
68    NodeValue* val;
69    
70    Node(int rl, int rr){
71        range_left = rl;
72        range_right = rr;
73        left = nullptr;
74        right = nullptr;
75        //length 0, count 1
76        val = new NodeValue(0, 1);
77    }
78    
79    int getRangeMid(){
80        return range_left + (range_right - range_left)/2;
81    }
82    
83    Node* getLeft(){
84        if(left == nullptr) left = new Node(range_left, getRangeMid());
85        return left;
86    }
87    
88    Node* getRight(){
89        if(right == nullptr) right = new Node(getRangeMid()+1, range_right);
90        return right;
91    }
92};
93
94//Approach 2: Segment Tree
95//https://leetcode.com/articles/number-of-longest-increasing-subsequence/
96//Runtime: 72 ms, faster than 52.97% of C++ online submissions for Number of Longest Increasing Subsequence.
97//Memory Usage: 60.9 MB, less than 11.11% of C++ online submissions for Number of Longest Increasing Subsequence.
98//time: O(NlogN), space: O(N)
99//segment tree
100class Tree{
101private:
102    NodeValue* merge(NodeValue* v1, NodeValue* v2){
103        if(v1->length == v2->length){
104            //we cannot accumulate the count of length 0 sequence
105            if(v1->length == 0) return new NodeValue(0, 1);
106            return new NodeValue(v1->length, v1->count + v2->count);
107        }
108        return (v1->length > v2->length) ? v1 : v2;
109    }
110    
111    void insert(Node* node, int key, NodeValue* value){
112        if(node->range_left == node->range_right){
113            //leaf node
114            node->val = merge(node->val, value);
115            return;
116        }
117        
118        if(key <= node->getRangeMid()){
119            //the queried key falls in left subtree
120            insert(node->getLeft(), key, value);
121        }else{
122            //the queried key falls in right subtree
123            insert(node->getRight(), key, value);
124        }
125        
126        node->val = merge(node->getLeft()->val, node->getRight()->val);
127    }
128    
129    NodeValue* query(Node* node, int key){
130        if(key >= node->range_right){
131            /*
132            we are querying [minv, key],
133            and current node's range is completely included in the query range
134            */
135            return node->val;
136        }else if(key < node->range_left){
137            //query range is outside the node's range
138            return new NodeValue(0, 1);
139        }
140        
141        return merge(query(node->getLeft(), key), query(node->getRight(), key));
142    }
143
144public:
145    Node* root;
146    
147    Tree(int rl, int rr){
148        root = new Node(rl, rr);
149    };
150    
151    //used outside
152    void insert(int key, NodeValue* value){
153        insert(root, key, value);
154    };
155    
156    NodeValue* query(int key){
157        return query(root, key);
158    };
159};
160
161class Solution {
162public:
163    int findNumberOfLIS(vector<int>& nums) {
164        if(nums.size() == 0) return 0;
165        int minv = INT_MAX, maxv = INT_MIN;
166        
167        for(int num : nums){
168            minv = min(minv, num);
169            maxv = max(maxv, num);
170        }
171        
172        Tree* tree = new Tree(minv, maxv);
173        for(int num : nums){
174            NodeValue* v = tree->query(num-1);
175            tree->insert(num, new NodeValue(v->length+1, v->count));
176        }
177        
178        return tree->root->val->count;
179    }
180};