Leetcode 673.Number of Longest Increasing Subsequence

原题地址

https://leetcode.com/problems/number-of-longest-increasing-subsequence/description/

题目描述

给定一个无序的数组,找出这个数组中包含的最长递增子序列的数目。(不是求最长递增子序列的长度,是问有几个最长递增子序列)

Example
Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].

思路

n为给定数组长度,L[ i ]表示以第i个(0<=i<=n-1)元素结尾的递增子序列能达到的长度,用动态规划的方法求出所有L[ i ],找出其中的最大值longest。
如果longest=1,说明每个单独的元素都是一个最长递增子序列,数组中所有元素都递减或者相等,此时直接返回数组长度n即可。
count[ i ]表示到达第i个元素且长度为L[ i ]的子序列的数目,初始全为0,i=1到n,每次扫描第i个元素之前的所有元素j,若元素j < 元素i,且L[ j ]+1=L[ i ],就增加count[ i ]的值:若count[ j ] 不为0,则加上count[ j ]的值;若count[ j ]=0则加1。
最后遍历求出的count数组,将L[ i ]=longest 的元素 i 对应的count[ i ]求和就是最后结果。
复杂度为 O(n^2)

代码

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        int L[n],count[n];
        int longest = 0;
        int result = 0;
        for (int j = 0; j < n; j++) {
            L[j] = 1;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && L[i] <= L[j] + 1) {
                    L[i] = L[j] + 1;
                }
            }
            if (longest < L[i]) {
                longest = L[i];
            }
        }

        if (longest == 1) {
            result = nums.size();
        } else {
            memset(count, 0, sizeof(L[0])*n);
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (nums[i] > nums[j] && L[i] == L[j] + 1 ) {
                        if (count[j] == 0) {
                            count[i] += 1;
                        } else {
                            count[i] += count[j];
                        }
                    }
                }
            }
            for (int i = 0; i < n; i++) {
                if (L[i] == longest) {
                    result += count[i];
                }
            }
        }
        return result;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。