[数据结构与算法]LeetCode 一周总结

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

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

方法一：动态规划。

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

则有转移方程：
$dp[i]=max(dp[j])+1,其中0\le j<i，且nums[j]<nums[i]$

$cnt[i]$为所有满足$dp[j]+1=dp[i]$且$0\le j<i$的$cnt[j]$的和。

最后，数组的最长递增子序列的长度$maxlen=max(dp[i])，其中0\le i<n$。
最长递增子序列的个数为$result=\sum (cnt[i])$，对于那些$i$满足$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]$为长度为$i$的递增序列的末位元素的最小值，用$len$表示目前最长递增序列的长度，$len$的起始值为1，$d[1]=num[0]$;

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

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

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

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

否则，在 $d$ 数组中二分查找，找到第一个比 $\text{nums}[i]$小的数 $d[k]$ ，并更新 $d[k+1]=\text{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;
    }
};