欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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给出了两种解法。第二种线段树的原因是因为各个增长的长度都可以看成一个段,涉及到段的更新可以考虑线段树。程序执行过程如图:(手绘的,太丑了,我的好好学学画图了......)

Number of Longest Increasing Subsequence

Number of Longest Increasing Subsequence

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