673. 最长递增子序列的个数

题目：给定一个未排序的整数数组，找到最长递增子序列的个数。

方法一：动态规划。

考虑前i个元素，令 d p [ i ] dp[i] dp[i]为以第 i i i个元素为结尾的最长递增子序列的长度，令 c n t [ i ] cnt[i] cnt[i]表示以第 i i i个元素为结尾的最长递增子序列的个数，这里nums[i]必须被选取。

则有转移方程：
d p [ i ] = m a x ( d p [ j ] ) + 1 , 其 中 0 ≤ j < i ， 且 n u m s [ j ] < n u m s [ i ] dp[i]=max(dp[j])+1,其中0≤j<i，且nums[j]<nums[i] dp[i]=max(dp[j])+1,其中0≤j<i，且nums[j]<nums[i]

c n t [ i ] cnt[i] cnt[i]为所有满足 d p [ j ] + 1 = d p [ i ] dp[j]+1=dp[i] dp[j]+1=dp[i]且 0 ≤ j < i 0≤j<i 0≤j<i的 c n t [ j ] cnt[j] cnt[j]的和。

最后，数组的最长递增子序列的长度 m a x l e n = m a x ( d p [ i ] ) ， 其 中 0 ≤ i < n maxlen=max(dp[i])，其中0≤i<n maxlen=max(dp[i])，其中0≤i<n。
最长递增子序列的个数为 r e s u l t = ∑ ( c n t [ i ] ) result=\sum(cnt[i]) result=∑(cnt[i])，对于那些 i i i满足 d p [ i ] = L dp[i]=L dp[i]=L。

代码：

int findNumberOfLIS(vector<int>& nums) {
        int n=nums.size();
        if(n==0) return 0;
        if(n==1) return 1;
        vector<int> dp(n);
        vector<int> cnt(n);
        dp[0]=1;
        cnt[0]=1;
        for(int i=1;i<n;i++)
        {
            cnt[i]=0;
            int max=0;
            for(int j=0;j<i;j++)
            {
                if(nums[i]>nums[j])
                {
                    if(dp[j]>max) max=dp[j];
                }
            }
            dp[i]=max+1;
            if(dp[i]==1) cnt[i]=1;
            else
            {
                for(int j=0;j<i;j++)
                {
                    if(nums[i]>nums[j] && dp[j]==max)
                    {
                    cnt[i]+=cnt[j];
                    }
                }
            }
        }
        int maxlen=0;
        int result=0;
        for(int i=0;i<n;i++)
        {
            if(dp[i]>maxlen) maxlen=dp[i];
        }
        for(int i=0;i<n;i++)
        {
            if(dp[i]==maxlen)
            {
                result+=cnt[i];
            }
        }
        return result;
    }

方法二：贪心算法+二分查找

（1）仅求最长递增序列长度：
想要递增的序列尽可能长，希望末位加上的数越小越好。令 d [ i ] d[i] d[i]为长度为 i i i的递增序列的末位元素的最小值，用 l e n len len表示目前最长递增序列的长度， l e n len len的起始值为1， d [ 1 ] = n u m [ 0 ] d[1]=num[0] d[1]=num[0];

证明，序列 d d d是关于 i i i是递增的。若 d [ j ] > d [ i ] d[j]>d[i] d[j]>d[i]且 j < i j<i j<i，则我们考虑从长度为 i i i的递增数列中删掉最后 i − j i-j i−j个数，可知长度为 i i i的序列的第 j j j个数小于 d [ i ] d[i] d[i]，从而小于 d [ j ] d[j] d[j]，由序列 d d d的定义可知矛盾。

遍历 n u m num num，更新 d d d和 l e n len len，若 n u m [ i ] ＞ d [ l e n ] num[i]＞d[len] num[i]＞d[len]，则 l e n = l e n + 1 len=len+1 len=len+1，否则，在 d [ 1 , 2 , . . . , l e n ] d[1,2,...,len] d[1,2,...,len]中找到 i i i，满足 d [ i − 1 ] < n u m [ j ] < d [ i ] d[i-1]<num[j]<d[i] d[i−1]<num[j]<d[i]，令 d [ i ] = n u m [ j ] d[i]=num[j] d[i]=num[j].根据 d d d的单调性，通过二分法查找合适的 i i i，优化时间复杂度。

总结：
对于 n u m s nums nums，按如下方法更新：
设当前已求出的最长上升子序列的长度为 len \textit{len} len（初始时为 1），从前往后遍历数组 nums \textit{nums} nums，在遍历到 nums [ i ] \textit{nums}[i] nums[i]时：

如果 nums [ i ] \textit{nums}[i] nums[i] > d [ len ] d[\textit{len}] d[len] ，则直接加入到 d d d 数组末尾，并更新 len = len + 1 \textit{len} = \textit{len} + 1 len=len+1；

否则，在 d d d 数组中二分查找，找到第一个比 nums [ i ] \textit{nums}[i] nums[i]小的数 d [ k ] d[k] d[k] ，并更新 d [ k + 1 ] = nums [ i ] d[k + 1] = \textit{nums}[i] d[k+1]=nums[i]。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = 1, n = (int)nums.size();
        if (n == 0) {
            return 0;
        }
        vector<int> d(n + 1, 0);
        d[len] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[len]) {
                d[++len] = nums[i];
            } else {
                int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                d[pos + 1] = nums[i];
            }
        }
        return len;
    }
};