Leetcode | 673. 最长递增子序列的个数
题目信息
解题思路
这个题除了需要计算最长递增子序列的长度，还需要计算最长递增子序列的数量。
所以我们可以在存储每个位置最长递增子序列的长度的基础上，增加一个数组记录每个位置上最长递增子序列的数量。
例如我们在计算i位置上的最长子序列，假设num[i] > num[i-1]，那么此时i位置上的最长递增子序列的长度应该是i-1位置上的子序列长度加一，那么此时i位置上最长递增子序列的数量应该和i-1位置上的子序列数量保持一致。
后面再和i-2位置上的数字比较时，假设num[i] > num[i-2]，并且i-2和i-1位置上的递增子序列的数量一致时，那么i位置上的最长递增子序列的数量应该是两者之和。
后面在i-3位置上的数字比较时，依次递推……
使用动态规划的思路解决这个题，状态转移的时候，有些地方需要多加注意，如果i位置上的数字大于之前的数字时，出现递增子序列：
- 如果此时的子序列长度大于已经有记录的子序列长度，则更新i位置的最长长度和重新统计
i位置上最长递增子序列的数量 - 这个长度的递增子序列已经有记录，直接更新
i位置上递增子序列的数量 - 最长递增子序列出现的位置不唯一，例如
[1,2,3,1,2,3,1,2,3]
代码
public int findNumberOfLIS(int[] nums) { // 数组的长度 int n = nums.length; // 记录每个位置上对应最长递增子序列的长度 int[] status = new int[n]; // 记录每个位置上对应最长递增子序列的个数 int[] count = new int[n]; // 每个长度的子序列对应的数量 int[] ans = new int[2001]; // 初始化操作，每个位置上的递增子序列长度和个数至少为1 for (int i = 0; i < n; i++) { status[i] = 1; count[i] = 1; } // 统计全局最长的递增子序列的长度 int max = 1; // 长度为1的递增子序列的个数就是数组的长度 ans[1] = n; // 统计每个位置上最长递增子序列的长度和个数 for (int i = 1; i < n; i++) { // 通过比较i位置上的数字和[0,i-1]位置上数字大小，计算递增子序列 int k = i - 1; while (k >= 0) { // 如果i位置上的数字大时，出现递增子序列， // 1、如果此时的子序列长度大于已经有记录的子序列长度，则更新i位置的最长长度和重新统计i位置上最长递增子序列的数量 // 2、这个长度的递增子序列已经有记录，直接更新i位置上递增子序列的数量 if (nums[i] > nums[k] && status[k] + 1 > status[i]) { status[i] = status[k] + 1; // 更新最长长度时，递增子序列的长度也要重新计算 count[i] = count[k]; // 更新全局最长的递增子序列的长度 max = Math.max(status[i], max); // 更新具有这个长度子序列的数量 ans[status[i]] += count[i]; } else if (nums[i] > nums[k] && status[k] + 1 == status[i]) { count[i] += count[k]; ans[status[i]] += count[k]; } --k; } } // 返回最长子串的数量 return ans[max]; }
结果
