最长递增序列个数

  1. public void sxy(){
  2.     int[] nums = {1,2,4,3,5,4,7,2};
  3.     int length = nums.length;
  4.     // 结尾长度
  5.     int[] dp = new int[length];
  6.     // 结尾数目
  7.     int[] cnt = new int[length];
  8.     int maxLength = 0;
  9.     int maxLengthIndex = 0;
  10.     for (int i=0; i<length;i++){
  11.         dp[i] = 1;
  12.         cnt[i] = 1;
  13.         int count = 1;
  14.         for(int j=0;j<i;j++){
  15.             if (nums[i]>nums[j]){
  16.                 int newV = dp[j] + 1;
  17.                 if (dp[i] == newV){
  18.                     count += cnt[j];
  19.                 }else if (dp[i] < newV){
  20.                     dp[i] = newV;
  21.                     // 重置count
  22.                     count = cnt[j];
  23.                 }
  25.             }
  26.         }
  27.         maxLength = Math.max(maxLength, dp[i]);
  29.         cnt[i] = count;
  30.     }
  31.     int result = 0;
  32.     for (int i =0; i<length;i++){
  33.         if (dp[i] == maxLength){
  34.             result += cnt[i];
  35.         }
  37.     }
  39.     System.out.println(result);
  40.     }

最长递增序列

  1.         int[] nums = {1, 3, 2, 7, 4, 9};
  2.         int[] dp = new int[nums.length];
  3.         dp[0] = 1;
  4.         int max = -1;
  5.         int length = nums.length;
  6.         for (int i = 1; i < length; i++){
  7.             for (int j = i - 1; j >= 0; j--)
  8.             if (nums[i] > nums[j]){
  9.                 dp[i] = Math.max(dp[j] + 1, dp[i]);
  10.             }
  11.             max = Math.max(dp[i], max);
  12.         }
  13.         System.out.println(max);