673. Number of Longest Increasing Subsequence最长递增子序列的数量

［抄题］：

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.

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

不知道为什么len[i] == len[j] + 1：因为可以间隔相加。

也不知道为什么是DP：原来小人是间隔着跳的。

［一句话思路］：

长度一个数组、数量一个数组，两个分开算

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

673. Number of Longest Increasing Subsequence最长递增子序列的数量

［一刷］：

如果出现了新的最长数组，count需要和最大长度一起换

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

count length分开算

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［算法思想：递归/分治/贪心］：贪心

［关键模板化代码］：

count更新或相加：

if (nums[j] < nums[i]) {
                    if (length[j] + 1 > length[i]) {
                        length[i] = length[j] + 1;
                        //renew cnt[i]
                        count[i] = count[j];
                    }else if (length[j] + 1 == length[i]) {
                        count[i] += count[j];
                    }
                }
            }

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

LIS本身

[代码风格] ：

class Solution {
    public int findNumberOfLIS(int[] nums) {
        //cc
        if (nums == null || nums.length == 0) return 0;
        
        //ini: length[], count[], res
        int n = nums.length, res = 0, max_len = 0;
        int[] length = new int[n]; 
        int[] count = new int[n];
        
        //for loop: i, nums[j] < nums[i], count j, max_length
        for (int i = 0; i < n; i++) {
            //; not ,
            length[i] = 1; count[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (length[j] + 1 > length[i]) {
                        length[i] = length[j] + 1;
                        //renew cnt[i]
                        count[i] = count[j];
                    }else if (length[j] + 1 == length[i]) {
                        count[i] += count[j];
                    }
                }
            }
            if (length[i] >  max_len) {
                max_len = length[i];
                //renew cnt[i]
                res = count[i];
            }   
            else if (length[i] ==  max_len) res += count[i];
        }
        
        return res;
    }
}

View Code

673. Number of Longest Increasing Subsequence最长递增子序列的数量

相关推荐