673. Number of Longest Increasing Subsequence

// LeetCode URL: https://leetcode.com/problems/number-of-longest-increasing-subsequence/
import java.util.Arrays;

/**
 * Dynamic Programming
 *
 * Lengths[i] = Longest Increasing Subsequence known at i (including ith
 * element)
 *
 * Counts[i] = Count of longest Increasing Subsequence known at i (including ith
 * element)
 *
 * for nums[i] > nums[j] ... 0 <= j < i, if lengths[i] == lengths[j]+1 ... then
 * just add nums[i] to the subsequence ending at jth position. Thus, add the
 * counts of the subsequences with the same max length known at i.
 *
 * If lengths[i] < length[j] + 1.. then new max Length at i is found... thus
 * update the length and counts at i.
 *
 * Time Complexity: O(N^2)
 *
 * Space Complexity: O(N)
 *
 * N = Length of input nums array.
 */
class Solution {
    public int findNumberOfLIS(int[] nums) {
        if (nums == null) {
            return 0;
        }
        if (nums.length <= 1) {
            return nums.length;
        }

        int[] lengths = new int[nums.length];
        int[] counts = new int[nums.length];
        Arrays.fill(lengths, 1);
        Arrays.fill(counts, 1);

        int maxCount = 1;
        int maxLen = 1;

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (lengths[i] == lengths[j] + 1) {
                        // Just adding the counts of the subsequences with same max length known at i.
                        counts[i] += counts[j];
                    } else if (lengths[i] < lengths[j] + 1) {
                        // New max length at i is found.
                        lengths[i] = lengths[j] + 1;
                        counts[i] = counts[j];
                    }
                }
            }
            if (maxLen == lengths[i]) {
                maxCount += counts[i];
            } else if (maxLen < lengths[i]) {
                maxLen = lengths[i];
                maxCount = counts[i];
            }
        }

        return maxCount;
    }
}