LeetCode 673.Number of Longest Increasing Subsequence

LeetCode 673.Number of Longest Increasing Subsequence

Description:

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences’ length is 1, so output 5.

分析：

动态规划问题：这道题我在之前的博客已写过，只是之前只需要返回最大长度，而这道题需要返回最大长度的个数。
增加一个vector容器counts用来记录最长递增子序列的个数。

例子分析：

输入Example 1: [1,3,5,4,7]
length[0]=length[1]=length[2]=length[3]=length[4]=1
counts[0]=counts[1]=counts[2]=counts[3]=counts[4]=1
根据算法步骤可得：
nums[0]=1, length[0]=1, counts[0]=1
nums[1]=3, length[1]=2, counts[1]=1
nums[2]=5, length[2]=3, counts[2]=1->1
nums[3]=4, length[3]=3, counts[3]=1->1
nums[4]=7, length[4]=4, counts[4]=1->1->1->2

代码如下：

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
	int findNumberOfLIS(vector<int>& nums) {
		if (nums.size() <= 1) return nums.size();
		vector<int> length(nums.size());// 最长递增子序列的长度
		vector<int> counts(nums.size());// 记录最长递增子序列的个数
		// 初始化置为1
		for (int i = 0; i < nums.size(); i++) {
			length[i] = 1;
			counts[i] = 1;
		}
		cout << counts[0] << endl;
		for (int i = 1; i < nums.size(); i++) {
			for (int j = 0; j < i; j++) {
				if (nums[i] > nums[j]) {
					if (length[i] < length[j] + 1) {
						length[i] = length[j] + 1;
						counts[i] = counts[j];
					}
					else if (length[i] == length[j] + 1) {
						counts[i] += counts[j];
					}
					cout << counts[i] << " ";
				}
			}
			cout << endl;
		}
		int max = 0, count = 0;
		for (int i = 0; i < nums.size(); i++) {
			// cout << counts[i] << " ";
			if (length[i] > max) {
				max = length[i];
			}
		}
		// cout << endl;
		for (int i = 0; i < nums.size(); i++) {
			if (length[i] == max) {
				count += counts[i];
			}
		}
		return count;
	}
};
int main() {
	Solution s;
	cout << "Input:" << endl;
	int n;
	cin >> n;
	vector<int> nums(n);
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	cout << "Output:" << endl;
	cout << "Answer: " << s.findNumberOfLIS(nums) << endl;
	return 0;
}

运行结果：

最长递增子序列问题可以参考我的另一篇博客最长递增子序列——动态规划