673. Number of Longest Increasing Subsequence

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