Similar to the Problem `#300 longest increase sequence`

, beyond that use a array `cnt[]`

to recode the ways to arrive `lis[i] (lis end at a[i)]`

. Here is the solution.

```
static int numOfLIS(int[] a) {
if (a == null || a.length == 0) return 0;
if (a.length < 2) return 1;
int[] dp = new int[a.length];
Arrays.fill(dp, 1);
int maxLen = 1;
int[] cnt = new int[a.length]; // cnt[i]: the ways that arrive the LIS end at a[i]
Arrays.fill(cnt, 1);
int res = 0;
for (int i = 1; i < a.length; i++) {
for (int j = i-1; j >= 0; j--) {
if (a[i] > a[j] && dp[j]+1 > dp[i])
dp[i] = dp[j]+1;
}
if (maxLen < dp[i]) maxLen = dp[i];
// compute cnt[i]
if (dp[i] > 1) { // dp[i] has changed from original 1 after traverse [0, i-1]
cnt[i] = 0; // for updated dp[i], cnt[i] is initialed as 0
for (int j = i-1; j >= 0; j--) {
if (a[i] > a[j] && dp[j]+1 == dp[i])
cnt[i] += cnt[j];
}
}
}
for (int i = 0; i < a.length; i++) {
if (dp[i] == maxLen) {
res += cnt[i];
}
}
return res;
}
```