673. Number of Longest Increasing Subsequence
1664 ワード
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[i]=len[j]+1といえばnums[j]で終わるlisを見つけて、次のnums[i]に続くとlen[i]になるので、count[j]のようなlisを複数見つけることができます.count[i]+=count[j];一方、len[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;
}
}