最长递增子序列的个数（树状数组，dp，leetcode673）-------------------c++实现_c++子序列个数

最长递增子序列的个数（树状数组，dp，leetcode673）-------------------c++实现

题目表述

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

注意 这个数列必须是 严格 递增的。

样例

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

条件

1 <= nums.length <= 2000
-106 <= nums[i] <= 106

思路

1.dp思路，算每一位的最长递增子序列，类似leetcode300，但是时间复杂度在O(n方);
2.树状数组
https://leetcode.cn/problems/number-of-longest-increasing-subsequence/solution/yi-bu-yi-bu-tui-dao-chu-zui-you-jie-fa-2-zui-chang/ 根据这个题解的思路做的问题

注意点

注意判断的细节(前一个数组的长度，当前数组的长度)

ac代码

1.dp代码参照leetcode300中的代码，做一个长度以及重复记录即可。
2.树状数组：

c++:

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
           vector<vector<int>> data,record;
           if(!nums.size())
           return 0;
           else
           {
               data.push_back({nums[0]});
                record.push_back({1});
           }
           //判断特殊情况以及第一个元素
           for(int i = 1;i < nums.size() ; i++)
           {
               int aim;  //所选中的要加入的列的前一列
               int front = 0;
                int rear = data.size()-1;
                int middle;
               if(nums[i]>data.back().back())
               {
            data.push_back({nums[i]});  //插入data中
            aim=data.size()-2;
               }
               else{
                   while(front<=rear)
                   {

                   middle = (front+rear)>>1;
                       if(data[middle].back()<nums[i])
                         front=middle+1;
                         else
                         rear=middle-1;
                   }                    //判断应该加入的是哪一列
               data[front].push_back(nums[i]);//插入data 中
              aim = front-1;
               }          
                    int lastnumber;    //lastnumber表述前一个数组中应该加的数
                      if(aim<0)
                      lastnumber=1;        
                   else{
                    front = 0;
                    rear = data[aim].size()-1;
                  
                   while(front<=rear)
                   {
                       middle = (front+rear)>>1;
                       if(data[aim][middle]>=nums[i])
                         front=middle+1;
                         else
                         rear=middle-1;
                   }       //front 为上一列第一个小于nums[i]的元素
                   if(!front)
                   lastnumber=record[aim].back();
                   else
                   lastnumber=record[aim].back()-record[aim][front-1];     
                          }
                          if(data[aim+1].size()==1)
                          record.push_back({lastnumber});
                          else
                          record[aim+1].push_back(record[aim+1].back()+lastnumber);       //判断是否是第aim+1列的第一个元素
           }
   
   return record.back().back();
    }
};
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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。