原题链接：

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

https://leetcode.cn/problems/number-of-longest-increasing-subsequence/description/

完成情况：

解题思路：

方法一：动态规划

方法二：贪心 + 前缀和 + 二分查找

参考代码：

__673最长递增子序列的个数__动态规划

package 西湖算法题解___中等题;public class __673最长递增子序列的个数__动态规划 {public int findNumberOfLIS(int[] nums) {//给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。//注意: 这个数列必须是 严格 递增的。严格大于。//注意是返回最长递增子序列的个数int numsLength = nums.length,maxLen = 0,res = 0;int dp_findNumberOfLIS [] = new int[numsLength];int count [] = new int[numsLength];for (int i = 0;idp_findNumberOfLIS[i] = 1;count[i] = 1;for (int j=0;jif (nums[i] > nums[j]){if (dp_findNumberOfLIS[j] + 1 > dp_findNumberOfLIS[i]){dp_findNumberOfLIS[i] = dp_findNumberOfLIS[j] + 1;count[i] = count[j];    //重置计数} else if (dp_findNumberOfLIS[j]+1 == dp_findNumberOfLIS[i]) {count[i]+=count[j];}}}if (dp_findNumberOfLIS[i] > maxLen){maxLen = dp_findNumberOfLIS[i];res = count[i];     //重制计数} else if (dp_findNumberOfLIS[i] == maxLen) {res += count[i];}}return res;}}

__673最长递增子序列的个数__贪心_前缀和_二分查找

package 西湖算法题解___中等题;import java.util.ArrayList;import java.util.List;public class __673最长递增子序列的个数__贪心_前缀和_二分查找 {public int findNumberOfLIS(int[] nums){List> d = new ArrayList>();List> cnt = new ArrayList>();for (int v : nums){int i = myBinarySearch1(d.size(),d,v);int c = 1;if (i > 0){int k = myBinarySearch2(d.get(i-1).size(),d.get(i-1),v);c = cnt.get(i-1).get(cnt.get(i-1).size()-1) - cnt.get(i-1).get(k);}if (i == d.size()){List dList = new ArrayList();dList.add(v);d.add(dList);List cntList = new ArrayList();cntList.add(0);cntList.add(c);cnt.add(cntList);}else {d.get(i).add(v);int cntSize = cnt.get(i).size();cnt.get(i).add(cnt.get(i).get(cntSize-1)+c);}}int size1 = cnt.size(),size2 = cnt.get(size1-1).size();return cnt.get(size1 - 1).get(size2-1);}private int myBinarySearch2(int n, List list, int target) {int left = 0,right = n;while (left < right){int mid = (left + right) /2;if (list.get(mid) < target){right = mid;}else {left = mid + 1;}}return left;}private int myBinarySearch1(int n, List> d, int target) {int left = 0,right = n;while (left < right){int mid = (left + right) /2;List list = d.get(mid);if (list.get(list.size() - 1) >= target){right = mid;}else {left = mid + 1;}}return left;}}

来源地址：https://blog.csdn.net/weixin_43554580/article/details/132471613