Number of Longest Increasing Subsequences

Share

Given integer array nums, return the number of longest increasing subsequences.

Example 1
Input: [1,3,5,4,7] → Output: 2 (both [1,3,5,7] and [1,3,4,7])
Example 2
Input: [2,2,2,2,2] → Output: 5

Solution Approach

Maintain two DP arrays: len[i] = LIS length ending at i, cnt[i] = count of such LIS. For each pair (i,j), update if we find better or equal LIS length.

  • len[i] = 1, cnt[i] = 1 initially.
  • For i from 1 to n-1: for j from 0 to i-1: if nums[j]
  • If len[j]+1 > len[i]: len[i]=len[j]+1, cnt[i]=cnt[j].
  • Elif len[j]+1 == len[i]: cnt[i]+=cnt[j].
  • maxLen = max(len[]); return sum of cnt[i] where len[i]==maxLen.
Java
class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length, maxLen = 0, result = 0;
        int[] len = new int[n], cnt = new int[n];
        java.util.Arrays.fill(len, 1); java.util.Arrays.fill(cnt, 1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (len[j] + 1 > len[i]) { len[i] = len[j]+1; cnt[i] = cnt[j]; }
                    else if (len[j] + 1 == len[i]) cnt[i] += cnt[j];
                }
            }
            maxLen = Math.max(maxLen, len[i]);
        }
        for (int i = 0; i < n; i++) if (len[i] == maxLen) result += cnt[i];
        return result;
    }
}
  • Time Complexity: O(N^2)
  • Space Complexity: O(N)