673. Number of Longest Increasing Subsequence

time: O(n^2)

space:O(n)

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int dp[] = new int[nums.length];
        int times[] = new int[nums.length];
        
        Arrays.fill(dp, 1);
        Arrays.fill(times, 1);
        
        int count = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    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];
                    }
                }
            }
        }
        // System.out.println(Arrays.toString(dp));
        // System.out.println(Arrays.toString(times));
        int maxLen = 0;
        int result = 0;
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] > maxLen) {
                // System.out.println("update max to:" + dp[i] + ",result times:" + times[i]);
                maxLen = dp[i];
                result = times[i];
            } else if (dp[i] == maxLen) { // same maxlen showing again
                // System.out.println("dp[i]:" + dp[i] + ",index:" + i + ",add times:" + times[i]);
                result += times[i];
            }
        }
        
        return result;
    }
}

/*
[1,2,4,3,5,4,7,2]
 1 2 3 3 4 4 5 2
 1 1 1 1 2 1 3 1
       x   x.   => find this one
 
 if (dp[j]+1 > dp[i]) {
    dp[i] = max(dp[i], dp[j]+1)
    times[i] = times[j]
 } else if (dp[j]+1 == dp[i])
    times[i] += times[j];
 }

1 3 5 4 7
1 2 3 3 4


2 2 2 2 2
1 1 1 1 1


*/