Java最长递增子序列的个数leetcode

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

注意 这个数列必须是 严格 递增的。

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        //当前最长子串长度
        int max = 1;
        for(int i = 0;i < n;i++){
            f[i] = 1;
            g[i] = 1;
            for(int j = 0;j < i;j++){
                if(nums[j] < nums[i]){
                    if(f[i] < f[j] + 1){
                        f[i] = f[j] + 1;
                        g[i] = g[j];
                    }else if(f[i] == f[j] + 1){
                        //找到了一个新的符合条件的前驱，此时将值继续累加到方案数当中
                        g[i] += g[j];
                    }
                }
            }
            max = Math.max(max,f[i]);
        }
        int res = 0;
        for(int i = 0 ;i < n;i++){
            if(f[i] == max){
                res += g[i];
            }
        }
        return res;
    }
}

执行用时：18 ms, 在所有 Java 提交中击败了72.27%的用户

内存消耗：41 MB, 在所有 Java 提交中击败了42.85%的用户