公司建设网站需要什么资质,昆山规划建设局网站,衡水企业网站设计,网站开发好还要空间吗673. 最长递增子序列的个数 原题链接#xff1a;完成情况#xff1a;解题思路#xff1a;方法一#xff1a;动态规划方法二#xff1a;贪心 前缀和 二分查找 参考代码#xff1a;__673最长递增子序列的个数__动态规划__673最长递增子序列的个数__贪心_前缀和_二分查找… 673. 最长递增子序列的个数 原题链接完成情况解题思路方法一动态规划方法二贪心 前缀和 二分查找 参考代码__673最长递增子序列的个数__动态规划__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;inumsLength;i){dp_findNumberOfLIS[i] 1;count[i] 1;for (int j0;ji;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){ListListInteger d new ArrayListListInteger();ListListInteger cnt new ArrayListListInteger();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()){ListInteger dList new ArrayListInteger();dList.add(v);d.add(dList);ListInteger cntList new ArrayListInteger();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, ListInteger 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, ListListInteger d, int target) {int left 0,right n;while (left right){int mid (left right) /2;ListInteger list d.get(mid);if (list.get(list.size() - 1) target){right mid;}else {left mid 1;}}return left;}
}
