Skip to content

673. Number of Longest Increasing Subsequence 👍

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  int findNumberOfLIS(vector<int>& nums) {
    const int n = nums.size();
    int ans = 0;
    int maxLength = 0;
    vector<int> length(n, 1);  // length[i] := LIS's length ending w/ nums[i]
    vector<int> count(n, 1);   // count[i] := # of the LIS ending w/ nums[i]

    // Calculate length and count arrays
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < i; ++j)
        if (nums[j] < nums[i])
          if (length[i] < length[j] + 1) {
            length[i] = length[j] + 1;
            count[i] = count[j];
          } else if (length[i] == length[j] + 1) {
            count[i] += count[j];
          }

    // Get # of LIS
    for (int i = 0; i < n; ++i)
      if (length[i] > maxLength) {
        maxLength = length[i];
        ans = count[i];
      } else if (length[i] == maxLength) {
        ans += count[i];
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
  public int findNumberOfLIS(int[] nums) {
    final int n = nums.length;
    int ans = 0;
    int maxLength = 0;
    int[] length = new int[n]; // length[i] := LIS's length ending w/ nums[i]
    int[] count = new int[n];  // count[i] := # of the LIS ending w/ nums[i]

    Arrays.fill(length, 1);
    Arrays.fill(count, 1);

    // Calculate length and count arrays
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < i; ++j)
        if (nums[j] < nums[i])
          if (length[i] < length[j] + 1) {
            length[i] = length[j] + 1;
            count[i] = count[j];
          } else if (length[i] == length[j] + 1) {
            count[i] += count[j];
          }

    // Get # of LIS
    for (int i = 0; i < n; ++i)
      if (length[i] > maxLength) {
        maxLength = length[i];
        ans = count[i];
      } else if (length[i] == maxLength) {
        ans += count[i];
      }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
  def findNumberOfLIS(self, nums: List[int]) -> int:
    ans = 0
    maxLength = 0
    length = [1] * len(nums)  # length[i] := LIS's length ending w/ nums[i]
    count = [1] * len(nums)  # count[i] := # of the LIS ending w/ nums[i]

    # Calculate length and count arrays
    for i, num in enumerate(nums):
      for j in range(i):
        if nums[j] < num:
          if length[i] < length[j] + 1:
            length[i] = length[j] + 1
            count[i] = count[j]
          elif length[i] == length[j] + 1:
            count[i] += count[j]

    # Get # Of LIS
    for i, l in enumerate(length):
      if l > maxLength:
        maxLength = l
        ans = count[i]
      elif l == maxLength:
        ans += count[i]

    return ans