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