Number of Longest Increasing Subsequence

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> len(n, 1), cnt(n, 1);
        int maxLen = 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 = max(maxLen, len[i]);
        }
        int total = 0;
        for (int i = 0; i < n; ++i) if (len[i] == maxLen) total += cnt[i];
        return total;
    }
};

func findNumberOfLIS(nums []int) int {
    n := len(nums)
    length := make([]int, n)
    cnt := make([]int, n)
    for i := range length {
        length[i] = 1
        cnt[i] = 1
    }
    maxLen := 1
    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] {
                if length[j]+1 > length[i] {
                    length[i] = length[j] + 1
                    cnt[i] = cnt[j]
                } else if length[j]+1 == length[i] {
                    cnt[i] += cnt[j]
                }
            }
        }
        if length[i] > maxLen {
            maxLen = length[i]
        }
    }
    total := 0
    for i := 0; i < n; i++ {
        if length[i] == maxLen {
            total += cnt[i]
        }
    }
    return total
}

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        length = [1] * n
        cnt = [1] * n
        max_len = 1
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if length[j] + 1 > length[i]:
                        length[i] = length[j] + 1
                        cnt[i] = cnt[j]
                    elif length[j] + 1 == length[i]:
                        cnt[i] += cnt[j]
            if length[i] > max_len:
                max_len = length[i]
        return sum(c for l, c in zip(length, cnt) if l == max_len)

function findNumberOfLIS(nums) {
    const n = nums.length;
    const length = new Array(n).fill(1);
    const cnt = new Array(n).fill(1);
    let maxLen = 1;
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (length[j] + 1 > length[i]) {
                    length[i] = length[j] + 1;
                    cnt[i] = cnt[j];
                } else if (length[j] + 1 === length[i]) {
                    cnt[i] += cnt[j];
                }
            }
        }
        if (length[i] > maxLen) maxLen = length[i];
    }
    let total = 0;
    for (let i = 0; i < n; i++) {
        if (length[i] === maxLen) total += cnt[i];
    }
    return total;
}

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] length = new int[n];
        int[] cnt = new int[n];
        Arrays.fill(length, 1);
        Arrays.fill(cnt, 1);
        int maxLen = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (length[j] + 1 > length[i]) {
                        length[i] = length[j] + 1;
                        cnt[i] = cnt[j];
                    } else if (length[j] + 1 == length[i]) {
                        cnt[i] += cnt[j];
                    }
                }
            }
            if (length[i] > maxLen) maxLen = length[i];
        }
        int total = 0;
        for (int i = 0; i < n; i++) {
            if (length[i] == maxLen) total += cnt[i];
        }
        return total;
    }
}

function findNumberOfLIS(nums: number[]): number {
    const n = nums.length;
    const length: number[] = new Array(n).fill(1);
    const cnt: number[] = new Array(n).fill(1);
    let maxLen = 1;
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (length[j] + 1 > length[i]) {
                    length[i] = length[j] + 1;
                    cnt[i] = cnt[j];
                } else if (length[j] + 1 === length[i]) {
                    cnt[i] += cnt[j];
                }
            }
        }
        if (length[i] > maxLen) maxLen = length[i];
    }
    let total = 0;
    for (let i = 0; i < n; i++) {
        if (length[i] === maxLen) total += cnt[i];
    }
    return total;
}