# Most Intutive O(N^2) Java DP Solution

• 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;
}``````

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