题目描述

给定一个整数数组 nums，你需要找到其中最长升序子序列（LIS, Longest Increasing Subsequence）的长度以及具有这个长度的升序子序列的个数。

注意：数组中的元素可能不是唯一的，且最长升序子序列的长度可能不止一个。

示例 1:

输入: nums = [1,3,5,4,7]
输出: 长度: 3, 个数: 2
解释: 两个最长升序子序列是 [1, 3, 5] 和 [1, 3, 7]。

示例 2:

输入: nums = [2,2,2,2,2]
输出: 长度: 1, 个数: 5
解释: 最长升序子序列的长度是 1，并且存在 5 个这样的子序列，即 [2], [2], [2], [2], [2]。

解题思路

这个问题可以通过动态规划解决。我们需要两个数组：

1. lengths：记录到当前位置为止，以当前元素结尾的最长升序子序列的长度。
2. counts：记录到当前位置为止，以当前元素结尾且长度为 lengths[i] 的最长升序子序列的个数。

另外，我们还需要一个辅助数组 prev 来记录每个元素的前一个元素索引，以便在统计个数时回溯。

PHP 代码示例

function findNumberOfLIS($nums) {
    $n = count($nums);
    if ($n <= 1) {
        return [$n, 1];
    }

    $lengths = array_fill(0, $n, 1);
    $counts = array_fill(0, $n, 1);
    $prev = array_fill(0, $n, -1);
    $maxLength = 1;
    $totalCounts = 0;

    for ($i = 1; $i < $n; $i++) {
        for ($j = 0; $j < $i; $j++) {
            if ($nums[$i] > $nums[$j]) {
                if ($lengths[$j] + 1 > $lengths[$i]) {
                    $lengths[$i] = $lengths[$j] + 1;
                    $counts[$i] = $counts[$j];
                    $prev[$i] = $j;
                } elseif ($lengths[$j] + 1 == $lengths[$i]) {
                    $counts[$i] += $counts[$j];
                    if ($prev[$i] == -1) {
                        $prev[$i] = $j;
                    }
                }
            }
        }
        if ($lengths[$i] > $maxLength) {
            $maxLength = $lengths[$i];
            $totalCounts = $counts[$i];
        } elseif ($lengths[$i] == $maxLength) {
            $totalCounts += $counts[$i];
        }
    }

    return [$maxLength, $totalCounts];
}

// 测试
$nums = [1, 3, 5, 4, 7];
$result = findNumberOfLIS($nums);
echo "长度: " . $result[0] . ", 个数: " . $result[1];

Python 代码示例

def findNumberOfLIS(nums):
    n = len(nums)
    if n <= 1:
        return [n, 1]

    lengths = [1] * n
    counts = [1] * n
    prev = [-1] * n
    maxLength = 1
    totalCounts = 0

    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                if lengths[j] + 1 > lengths[i]:
                    lengths[i] = lengths[j] + 1
                    counts[i] = counts[j]
                    prev[i] = j
                elif lengths[j] + 1 == lengths[i]:
                    counts[i] += counts[j]

        if lengths[i] > maxLength:
            maxLength = lengths[i]
            totalCounts = counts[i]
        elif lengths[i] == maxLength:
            totalCounts += counts[i]

    return [maxLength, totalCounts]

# 测试
nums = [1, 3, 5, 4, 7]
result = findNumberOfLIS(nums)
print("长度:", result[0], "个数:", result[1])

JavaScript 代码示例

function findNumberOfLIS(nums) {
    const n = nums.length;
    if (n <= 1) {
        return [n, 1];
    }

    const lengths = new Array(n).fill(1);
    const counts = new Array(n).fill(1);
    const prev = new Array(n).fill(-1);
    let maxLength = 1;
    let totalCounts = 0;

    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                if (lengths[j] + 1 > lengths[i]) {
                    lengths[i] = lengths[j] + 1;
                    counts[i] = counts[j];
                    prev[i] = j;
                } else if (lengths[j] + 1 === lengths[i]) {
                    counts[i] += counts[j];
                }
            }
        }
        if (lengths[i] > maxLength) {
            maxLength = lengths[i];
            totalCounts = counts[i];
        } else if (lengths[i] === maxLength) {
            totalCounts += counts[i];
        }
    }

    return [maxLength, totalCounts];
}

// 测试
const nums = [1, 3, 5, 4, 7];
const result = findNumberOfLIS(nums);
console.log(`长度: ${result[0]}, 个数: ${result[1]}`);

码小课网站中有更多相关内容分享给大家学习，希望以上内容对你有所帮助！