天峻县公司网站建设,宣传册设计一般多少钱,建站行业的乱象,ciid中国室内设计官网1. 题目
给定一个未排序的整数数组#xff0c;找到最长递增子序列的个数。
示例 1:
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列#xff0c;分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。示例 2:
输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1#xff0c;…1. 题目
给定一个未排序的整数数组找到最长递增子序列的个数。
示例 1:
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。示例 2:
输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1并且存在5个子序列的长度为1因此输出5。
注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。来源力扣LeetCode 链接https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目动态规划应用–最长递增子序列 LeetCode 300
本题不仅要求最长子序列还要求个数使用两个dp数组一个记录以 i 结束的最大长度dp[i]一个记录以 i 结束的最长子序列的个数
class Solution { // C
public:int findNumberOfLIS(vectorint nums) {int i, j, n nums.size();int maxlen 1, sum 0;vectorint dp(n, 1);vectorint count(n, 1);for(i 1; i n; i){for(j i-1; j 0; --j){if(nums[i] nums[j]){if(dp[j]1 dp[i]){dp[i] dp[j]1;count[i] count[j];//更新为count[j]}else if(dp[j]1 dp[i])count[i] count[j];//与count[j]相加}}maxlen max(maxlen, dp[i]);}for(i 0; i n; i)if(dp[i]maxlen)sum count[i];return sum;}
};84 ms 12.7 MB
class Solution:def findNumberOfLIS(self, nums: List[int]) - int:n len(nums)maxlen 1dp [1]*ncount [1]*nfor i in range(1,n):for j in range(i):if nums[i] nums[j]:if dp[j]1 dp[i]:dp[i] dp[j]1count[i] count[j]elif dp[j]1 dp[i]:count[i] count[j]maxlen max(maxlen, dp[i])ans 0for i in range(n):if dp[i]maxlen:ans count[i]return ans812 ms 13.8 MB
题解区还有nlogn解法线段树树状数组等
