673. 最长递增子序列的个数-Toy模板网

这篇具有很好参考价值的文章主要介绍了673. 最长递增子序列的个数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

原题链接：

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

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

完成情况：

673. 最长递增子序列的个数,算法知识,# LeetCode题解,java学习,代理模式,java,算法,数据结构,leetcode

解题思路：

方法一：动态规划

673. 最长递增子序列的个数,算法知识,# LeetCode题解,java学习,代理模式,java,算法,数据结构,leetcode

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

673. 最长递增子序列的个数,算法知识,# LeetCode题解,java学习,代理模式,java,算法,数据结构,leetcode 文章来源地址https://www.toymoban.com/news/detail-669875.html

参考代码：

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;
	}
}