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

动态规划

class Solution {
    
    public int findNumberOfLIS(int[] nums) {
    
       int n = nums.length;
       //0 维表示以nums[i]结尾的最长子序列长度 1 维 表示以nums[i]结尾的最长子序列个数
       int[][] dp = new int[n][2];
       dp[0][0] = 1;
       dp[0][1] = 1;
       int maxlen = 1;
       int maxnum = 1;
       for(int i = 1; i < n;i++){
    
           dp[i][0] = 1;
           dp[i][1] = 1;
           for(int j = 0; j < i;j++){
    
              if(nums[j] < nums[i]){
    
                  //dp[i] = Math.max(dp[i],dp[j] +1);
                  if(dp[j][0]+1 == dp[i][0]){
    
                      dp[i][1] += dp[j][1];
                  }
                  if(dp[j][0]+1 > dp[i][0]){
    
                      dp[i][0] = dp[j][0] + 1;
                      dp[i][1] = dp[j][1];
                  }
              }
           }
           if(dp[i][0] == maxlen)
                maxnum += dp[i][1];
            if(dp[i][0] > maxlen){
    
                maxlen = dp[i][0];
                maxnum = dp[i][1];
            }
          
       }
       return maxnum;
    }
}

贪心 + 前缀和 + 二分查找

class Solution {
    
    public int findNumberOfLIS(int[] nums) {
    
       int n = nums.length;
       //val.get(i) 存放了长度为i+1的递增子序列 的末尾元素 val.get(i) 单调不增
       List<List<Integer>> val = new ArrayList<>();
       List<List<Integer>> presum = new ArrayList<>();
       List<Integer> val0 = new ArrayList<>();
       val0.add(nums[0]);
       List<Integer> presum0 = new ArrayList<>();
       presum0.add(1);
       val.add(val0);
       presum.add(presum0);
       int left = 0;
       int right = 0;
       int maxlen = 1;
       int maxsum = 1;
       for(int i = 1; i < n;i++){
    
           int l = left;
           int r = right;
           while(l < r){
    
               int m = l + (r - l +1) / 2;
               int len = val.get(m).size();
               if(val.get(m).get(len-1) < nums[i])
                  l = m;
               else
                  r = m-1;
           }
           if(val.get(l).get(val.get(l).size()-1) >= nums[i]){
    
               val.get(l).add(nums[i]);
               presum.get(l).add(presum.get(l).get(presum.get(l).size()-1)+1);
               if(l+1 == maxlen)
                 maxsum += 1;
           }
           else{
    
               System.out.println("****");
               List<Integer> smallVal = val.get(l);
               List<Integer> smallPre = presum.get(l);
               int l1 = 0;
               int r1 = smallVal.size() - 1;
               while(l1 < r1){
    
                  int m1 = l1 + (r1-l1) / 2;
                  if(smallVal.get(m1) >= nums[i]){
    
                      l1 = m1+1;
                  }
                  else{
    
                      r1 = m1;
                  }
               }
               int pre = 0;
               if(l1 == 0)
                 pre = smallPre.get(smallPre.size()-1);
               else
                 pre = smallPre.get(smallPre.size()-1) - smallPre.get(l1-1) ;
                System.out.println(pre);
               if(right < l+1){
    
                   List<Integer> newval = new ArrayList<>();
                    List<Integer> newpre = new ArrayList<>();
                    newval.add(nums[i]);
                    newpre.add(pre);
                    val.add(newval);
                    presum.add(newpre);
                    right = l+1;
               }else{
    
                   int lastpre = presum.get(l+1).get( presum.get(l+1).size()-1);
                   val.get(l+1).add(nums[i]);
                   presum.get(l+1).add(pre+lastpre);
               }
               if(l+2 == maxlen)
                  maxsum += pre;
                if(l+2 > maxlen){
    
                   maxlen = l+2;
                   maxsum = pre;
                }
           }
       }
       return maxsum;

    }
}