golang刷leetcode动态规划（5）lis 最长递增子序列

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

func findNumberOfLIS(nums []int) int {
  if len(nums) < 1 {
    return 0
  }
  l := make([]int, len(nums))
  c := make([]int, len(nums))
  max := 0
  for i := 0; i < len(nums); i++ {
    l[i] = 1
    c[i] = 1
  }
  for i := 1; i < len(nums); i++ {
    for j := 0; j < i; j++ {
      if nums[j] < nums[i] {
        if l[i] < l[j]+1 {
          l[i] = l[j] + 1
          c[i] = c[j]
        } else if l[i] == l[j]+1 {
          c[i] = c[j] + 1
        }
      }
    }
    if max < l[i] {
      max = l[i]
    }
  }
  sum := 0
  for i := 0; i < len(nums); i++ {
    if l[i] == max {
      sum += c[i]
    }
  }
  return sum
}