Number of Longest Increasing Subsequence
程序员文章站
2022-06-06 15:53:44
...
Given an unsorted array of integers, find the number of longest increasing subsequence.
Example 1:
Input: [1,3,5,4,7] Output: 2 Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].
Example 2:
Input: [2,2,2,2,2] Output: 5 Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.思路:这道题有动态规划和线段树两种方案。
LeetCode给出了两种解法。第二种线段树的原因是因为各个增长的长度都可以看成一个段,涉及到段的更新可以考虑线段树。程序执行过程如图:(手绘的,太丑了,我的好好学学画图了......)
class Solution {
class Value{
public int length;
public int count;
public Value(int length ,int count){
this.length = length;
this.count = count;
}
}
class Node{
int left;
int right;
Node lnode;
Node rnode;
Value value;
public Node(int start,int end){
left = start;
right = end;
lnode = null;
rnode = null;
value = new Value(0,1);
}
public int getmid(){
return left + (right - left)/2;
}
public Node getleft(){
if(lnode == null) lnode = new Node(left,getmid());
return lnode;
}
public Node getright(){
if(rnode == null) rnode = new Node(getmid()+1,right);
return rnode;
}
}
public Value merge(Value v1 ,Value v2){
if(v1.length == v2.length){
if(v1.length == 0) return new Value(0,1);
return new Value(v1.length,v1.count + v2.count);
}
return v1.length > v2.length?v1:v2;
}
public void insert(Node n,int key,Value value){
if(n.left == n.right){
n.value = merge(n.value,value);
return;
}else if(key <= n.getmid()){
insert(n.getleft(),key,value);//不能用lnode,因为可能为null
}else{
insert(n.getright(),key,value);
}
n.value = merge(n.getleft().value,n.getright().value);
}
public Value query(Node node,int key){
if(node.left > key){
return new Value(0,1);
}else if(node.right <= key){
return node.value;
}else{
//不确定结果在哪一支所以都要查询,
return merge(query(node.getleft(),key),query(node.getright(),key));
}
}
public int findNumberOfLIS(int[] nums) {
int len = nums.length;
if(len == 0) return 0;
int min = nums[0];
int max = nums[0];
for(int i = 0 ;i < len ;i++){
min = Math.min(min,nums[i]);
max = Math.max(max,nums[i]);
}
Node root = new Node(min,max);
for(int num:nums){
Value v = query(root,num - 1);
insert(root,num,new Value(v.length+1,v.count));
}
return root.value.count;
}
}
上一篇: 字符串长度问题
推荐阅读
-
最长上升子序列(LIS: Longest Increasing Subsequence)
-
【每日一道算法题】Leetcode之longest-increasing-path-in-a-matrix矩阵中的最长递增路径问题 Java dfs+记忆化
-
Longest Increasing Path in a Matrix
-
LintCode 667: Longest Palindromic Subsequence (DP 经典题)
-
【dp-LIS】牛客网 --最长上升子序列 POJ 2533--Longest Ordered Subsequence(LIS模板题)
-
最长递增子序列(Longest Increasing Subsequence)
-
最长上升子序列(LIS: Longest Increasing Subsequence)
-
最长上升子序列 Longest Increasing Subsequence 输出其中一个序
-
Hbase read performance with increasing number of client threads
-
Longest Increasing Subsequence最长增长子序列