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

原题链接：

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;i<numsLength;i++){dp_findNumberOfLIS[i] = 1;count[i] = 1;for (int j=0;j<i;j++){if (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<List<Integer>> d = new ArrayList<List<Integer>>();List<List<Integer>> cnt = new ArrayList<List<Integer>>();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<Integer> dList = new ArrayList<Integer>();dList.add(v);d.add(dList);List<Integer> cntList = new ArrayList<Integer>();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);}/**** @param n* @param list* @param target* @return*/private int myBinarySearch2(int n, List<Integer> 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;}/*** * @param n* @param d* @param target* @return*/private int myBinarySearch1(int n, List<List<Integer>> d, int target) {int left = 0,right = n;while (left < right){int mid = (left + right) /2;List<Integer> list = d.get(mid);if (list.get(list.size() - 1) >= target){right = mid;}else {left = mid + 1;}}return left;}
}