Задача: 673. Number of Longest Increasing Subsequence
Сложность: medium

Дан массив целых чисел 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.

😎 Решение:

class Solution {
    function findNumberOfLIS($nums) {
        $n = count($nums);
        $length = array_fill(0, $n, 1);
        $count = array_fill(0, $n, 1);

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

        $maxLength = max($length);
        $result = 0;

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

        return $result;
    }
}

Ставь 👍 и забирай 📚 Базу знаний