How many longest increasing subsequences

def count_longest_increasing(nums):
    n = len(nums)
    length, count = [1] * n, [1] * n         # best length ending at i, and how many reach it
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                if length[j] + 1 > length[i]:
                    length[i], count[i] = length[j] + 1, count[j]
                elif length[j] + 1 == length[i]:
                    count[i] += count[j]
    best = max(length)
    return sum(c for l, c in zip(length, count) if l == best)

#include <algorithm>
#include <vector>

long long solve(const std::vector<int>& nums) {
    const int n = nums.size();
    std::vector<int> len(n, 1);
    std::vector<long long> cnt(n, 1);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < i; ++j) {
            if (nums[j] >= nums[i]) continue;
            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];
        }
    int best = *std::max_element(len.begin(), len.end());
    long long total = 0;
    for (int i = 0; i < n; ++i) if (len[i] == best) total += cnt[i];
    return total;
}

class Solution {
    public long countLongestIncreasing(int[] nums) {
        int n = nums.length, best = 0;
        int[] len = new int[n];
        long[] cnt = new long[n];
        for (int i = 0; i < n; i++) {
            len[i] = 1; cnt[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] >= nums[i]) continue;
                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];
            }
            best = Math.max(best, len[i]);
        }
        long total = 0;
        for (int i = 0; i < n; i++) if (len[i] == best) total += cnt[i];
        return total;
    }
}

function countLongestIncreasing(nums) {
  const n = nums.length, len = new Array(n).fill(1), cnt = new Array(n).fill(1);
  for (let i = 0; i < n; i++)
    for (let j = 0; j < i; j++) {
      if (nums[j] >= nums[i]) continue;
      if (len[j] + 1 > len[i]) { len[i] = len[j] + 1; cnt[i] = cnt[j]; }   // a longer chain
      else if (len[j] + 1 === len[i]) cnt[i] += cnt[j];                    // another chain as long
    }
  const best = Math.max(...len);
  return len.reduce((s, l, i) => s + (l === best ? cnt[i] : 0), 0);
}

fn solve(nums: &[i64]) -> i64 {
    let n = nums.len();
    let (mut len, mut cnt) = (vec![1i64; n], vec![1i64; n]);
    for i in 0..n {
        for j in 0..i {
            if nums[j] >= nums[i] {
                continue;
            }
            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];
            }
        }
    }
    let best = *len.iter().max().unwrap();
    (0..n).filter(|&i| len[i] == best).map(|i| cnt[i]).sum()
}

import Data.Array

solve :: [Int] -> Int
solve nums = sum [c | (l, c) <- elems table, l == best]
  where
    n = length nums
    a = listArray (0, n - 1) nums
    -- table ! i = (longest length ending at i, number of subsequences reaching it)
    table = listArray (0, n - 1) (map entry [0 .. n - 1]) :: Array Int (Int, Int)
    entry i = foldl offer (1, 1) [table ! j | j <- [0 .. i - 1], a ! j < a ! i]
    offer (l, c) (lj, cj)
      | lj + 1 > l = (lj + 1, cj)
      | lj + 1 == l = (l, c + cj)
      | otherwise = (l, c)
    best = maximum (map fst (elems table))