LeetCode673

LeetCode每日一题2021.9.20

思路

在最长上升子序列的转移时,维护一个 cnt 数组,表示以 i 结尾的最长上升子序列个数

f[i] 表示以 i 结尾的最长上升子序列的长度

转移方程为 cnt[i] = (f[i] == f[j] + 1 ? cnt[i] + cnt[j] : cnt[j]);

当f[i] < f[j] + 1的时候, 此时以 i 结尾的最长上升子序列个数显然会被更新,因此直接赋值即可

当f[i] = f[j] + 1的时候, 此时以 i 结尾的最长上升子序列个数需要累加上cnt[j]

AC_CODE

const int N = 2020;

#define n a.size()

class Solution {

public:

    int f[N] = {0}, cnt[N] = {0};

    int findNumberOfLIS(vector<int>& a) {

        int res = 0;

        for(int i = 0; i < n; i ++ ) {

            f[i] = cnt[i] = 1;

            for(int j = 0; j < i; j ++ ) {

                if(a[j] < a[i]) {

                    if(f[i] < f[j] + 1) {

                        f[i] = f[j] + 1;

                        cnt[i] = cnt[j];

                    } else if(f[i] == f[j] + 1) {

                        cnt[i] += cnt[j];

                    }

                }

            }

            res = max(res, f[i]);

        }

        int ans = 0;

        for(int i = 0; i < n; i ++ )

            ans += (f[i] == res) * cnt[i];

        return ans;

    }

};

巴特西

LeetCode673

LeetCode每日一题2021.9.20

思路

AC_CODE

最新文章

热门文章