LWC 49：673. Number of Longest Increasing Subsequence

用户1147447

发布于 2019-05-26 09:18:59

3380

发布于 2019-05-26 09:18:59

文章被收录于专栏：机器学习入门机器学习入门

LWC 49：673. Number of Longest Increasing Subsequence

传送门：673. Number of Longest Increasing Subsequence

Problem:

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

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

Example 2:

Input: 2,2,2,2,2 Output: 5 Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences’ length is 1, so output 5.

Note:

Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

题意：最长递增子序列的升级版，求最大长度下，总共有多少条路径。

比如：

1 2 4 3 5 4 7 2

1 2   3 5   7
1 2 4   5   7
1 2   3   4 7

所以总共有三条，抽象成结点和边的关系为：
1 -> 2 -> 4 -> 5 -> 7
       -> 3 -> 5 
            -> 4 -> 7

从横切面来看，无非就是求解结点从一阶段转移到下一阶段的最大边数。

所以可以定义状态cnt[i]表示，当且位置下，达到最长递增子序列所需的边数

if (如果下一阶段再一次取得最长递增长度)　说明有新的路径产生
    cnt[i] += cnt[j]  j < i
if (如果第一次更新最长递增长度)　之前累加的cnt[i]都必须清零
    cnt[i] = cnt[j]   j < i

代码如下：

    public int findNumberOfLIS(int[] nums) {
        int n = nums.length, max_len = 0;
        int[] len = new int[n];
        int[] cnt = new int[n];
        for (int i = 0; i < n; ++i) {
            len[i] = 1;
            cnt[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    if (len[i] == len[j] + 1) cnt[i] += cnt[j];
                    else if (len[i] < len[j] + 1) {
                        len[i] = len[j] + 1;
                        cnt[i] = cnt[j];
                    }
                }
                max_len = Math.max(max_len, len[i]);
            }
        }

        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (len[i] == max_len) res += cnt[i];
        }
        return res;
    }

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017年09月10日，如有侵权请联系 cloudcommunity@tencent.com 删除

bit