Useful link:http://www.cnblogs.com/grandyang/p/7603903.html
lens[i]:以nums[i]结尾的LIS的长度
count[i]: 以nums[i]结尾的LIS的个数
maxLen: 最长LIS长度
注意遍历时没次lens[i], count[i]初始化为1. 转换方程时通过看i前面的j, 如果nums[i] > nums[j]时，len[i], len[j]有什么关系。
如果说len[i] = len[j] + 1,说明我们可以找到以nums[j]结尾的lis, 然后再接上一个nums[i]就变成len[i]了,所以我们可以再找到count[j]那么多个这样的lis. 于是count[i] += count[j]; 而如果len[i] < len[j] + 1, 说明我们找到了比lens[i]更长的lis,所以len[i]更新为len[j] + 1, count[i]被更新为count[j].
最后注意，找到len[i] == maxLen的时候，res 不是res++, 而是 res + count[i].
class Solution {
public int findNumberOfLIS(int[] nums) {
if (nums == null || nums.length == 0){
return 0;
}
int[] lens = new int[nums.length];
int[] count = new int[nums.length];
int maxLen = 0;
for (int i = 0; i < nums.length; i++){
lens[i] = 1;
count[i] = 1;
for (int j = 0; j < i; j++){
if (nums[i] > nums[j]){
if (lens[i] == lens[j] + 1){
count[i] += count[j];
} else if (lens[i] < lens[j] + 1){
lens[i] = lens[j] + 1;
count[i] = count[j];
}
}
}
maxLen = Math.max(maxLen,lens[i]);
}
int res = 0;
for (int i = 0; i < lens.length; i++){
if (lens[i] == maxLen){
res += count[i];
}
}
return res;
}
}
