Number of Longest Increasing Subsequence LeetCode solution in Java

1
class Solution {
2
  public int findNumberOfLIS(int[] nums) {
3
    int N = nums.length;
4
    int[] dp = new int[N];
5
    int[] count = new int[N];
6
    Arrays.fill(dp, 1);
7
    Arrays.fill(count, 1);
8
    int maxi = 1;
9
    for (int i = 0; i < N; i++) {
10
      for (int j = 0; j < i; j++) {
11
        if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
12
          dp[i] = dp[j] + 1;
13
          // inherit a new one
14
          count[i] = count[j];
15
          maxi = Math.max(dp[i], maxi);
16
        } else if (nums[j] < nums[i] && dp[j] + 1 == dp[i]) {
17
          // got one as same len, increase count
18
          count[i] += count[j];
19
        }
20
      }
21
    } // for ends
22
    int maxlis = 0;
23
    for (int i = 0; i < N; i++) {
24
      if (maxi == dp[i]) {
25
        maxlis += count[i];
26
      }
27
    }
28
    return maxlis;
29
  }
30
}