【算法分析与设计】【第十一周】673. Number of Longest Increasing Subsequence

题目来源：673：

动态规划基础训练。

673. Number of Longest Increasing Subsequence

题目大意

求出一个无序整数数组的最长递增子序列的数量。

题目有点绕，其实分解一下就是：
（1）求出最长递增子序列的长度len
（2）求长度为len的递增子序列有几条
题目就是求这个条数。

思路

其实本质是最长递增子序列问题（LIS）。
只要在求最长递增子序列长度的同时计数就可以了。

LIS简单回顾

关于LIS可参考《算法概论》P157

算法

for j = 1, 2, ..., n
  L(j) = 1 + max{L(i):(i, j)∈E}
return maxjL(j)

解题代码

class Solution {
public:
  int findNumberOfLIS(vector<int>& nums) {
    int n = nums.size();

    // handle special case
    if (n <= 1) return n;

    int length[n] = {1};  // length[i] : the length of the seq ends with the ith element
    int count[n] = {1};  // count[i] : the number of seqs of length i
    for (int i = 0; i < n; i++) length[i] = count[i] = 1;

    for (int j = 0; j < n; j++) {
      for (int i = 0; i < j; i++) {
        if (nums[j] > nums[i]) {
          if (length[i] >= length[j]) {
            // add nums[j] into the seq which ends with the ith element, and the length becomes length[i]+1
            length[j] = length[i] + 1;
            count[j] = count[i];
          } else if (length[i] + 1 == length[j]) {
            // merge two seqs
            count[j] += count[i];
          }
        }
      }
    }

    int maxLen = 0;
    for (int i = 0; i < n; i++) {
      if (length[i] > maxLen) maxLen = length[i];
    }
    int re = 0;
    for (int i = 0; i < n; i++) {
      if (length[i] == maxLen) {
        re += count[i];
      }
    }
    return re;
  }
};

时间复杂度

O(n^2)