Simple Java solution based on DP


  • 0
    T

    The basic idea is to use two arrays, dp[n] and times[n], to record the length of longest increasing sequence and the times of this length, respectively.

        public int findNumberOfLIS(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            int[] dp = new int[nums.length];
            int[] times = new int[nums.length];
            Arrays.fill(dp, 1); 
            Arrays.fill(times, 1);
            for (int i = 1; i < nums.length; i++) {
                for (int j = 0; j < i; j++) {
                    if (nums[j] < nums[i]) {
                        if (dp[j] + 1 > dp[i]) {
                            dp[i] = dp[j] + 1;
                            times[i] = times[j];
                        } else if (dp[j] + 1 == dp[i]) {
                            times[i] += times[j];
                        }
                    }
                }
            }
            int max = 0, time = 0;
            for (int i = 0; i < dp.length; i++) {
                if (dp[i] > max) {
                    max = dp[i];
                    time = times[i];
                } else if (dp[i] == max) {
                    time += times[i];
                }
            }
            return time;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.