#ЛитКод
Задача: 673. Number of Longest Increasing Subsequence

Дан массив целых чисел nums, верните количество самых длинных строго возрастающих подпоследовательностей.

Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

👨‍💻 Алгоритм:

1⃣Объявите два массива динамического программирования length и count, и инициализируйте их значениями length[i]=1 и count[i]=1. Итерируйте i от 0 до n−1. Для каждого i итерируйте j от 0 до i−1 и, если nums[j] < nums[i], обновите length[i] и count[i] в зависимости от значений length[j] и count[j].

2⃣Найдите максимальное значение в массиве length и сохраните его в переменной maxLength. Инициализируйте переменную result = 0.

3⃣Итерируйте i от 0 до n−1 и, если length[i] = maxLength, добавьте count[i] к result. Верните result.

😎 Решение:

var findNumberOfLIS = function(nums) {
    let n = nums.length;
    let length = new Array(n).fill(1);
    let count = new Array(n).fill(1);

    for (let i = 0; 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;
                    count[i] = 0;
                }
                if (length[j] + 1 === length[i]) {
                    count[i] += count[j];
                }
            }
        }
    }

    let maxLength = Math.max(...length);
    let result = 0;

    for (let i = 0; i < n; i++) {
        if (length[i] === maxLength) {
            result += count[i];
        }
    }

    return result;
}

👉Новости 👉Платформа