宁波专业网站定制制作服务,qq轻聊版,做网站免费的域名,做瞹瞹瞹视频网站代码随想录算法训练营第8周#xff08;C语言#xff09;|Day56#xff08;动态规划#xff09;
Day56、动态规划#xff08;包含题目 ● 300.最长递增子序列 ● 674. 最长连续递增序列 ● 718. 最长重复子数组 #xff09;
300.最长递增子序列
题目描述
给你一个整数… 代码随想录算法训练营第8周C语言|Day56动态规划
Day56、动态规划包含题目 ● 300.最长递增子序列 ● 674. 最长连续递增序列 ● 718. 最长重复子数组
300.最长递增子序列
题目描述
给你一个整数数组 nums 找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
题目解答
int lengthOfLIS(int* nums, int numsSize) {int *dp(int*)malloc(sizeof(int)*numsSize);int res0;dp[0]1;for(int i1;inumsSize;i){dp[i]1;for(int j0;ji;j){if(nums[j]nums[i]){dp[i]fmax(dp[i],dp[j]1);}}resfmax(dp[i],res);}return res;
}题目总结
dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度。
674. 最长连续递增序列
题目描述
给定一个未经排序的整数数组找到最长且 连续递增的子序列并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 rl r确定如果对于每个 l i r都有 nums[i] nums[i 1] 那么子序列 [nums[l], nums[l 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。
题目解答
int findLengthOfLCIS(int* nums, int numsSize) {if(numsSize1){return 1;}int *dp(int*)malloc(sizeof(int)*numsSize);int res0;dp[0]1;for(int i1;inumsSize;i){if(nums[i]nums[i-1]){dp[i]dp[i-1]1;}else{dp[i]1;}resfmax(res,dp[i]);}return res;
}题目总结
dp[i]以下标i为结尾的连续递增的子序列长度为dp[i]。。
718. 最长重复子数组
题目描述
给两个整数数组 A 和 B 返回两个数组中公共的、长度最长的子数组的长度。
题目解答
int findLength(int* nums1, int nums1Size, int* nums2, int nums2Size) {int**dp(int**)malloc(sizeof(int*)*(nums1Size1));for(int i0;inums1Size1;i){dp[i](int*)malloc(sizeof(int)*(nums2Size1));}for(int i0;inums1Size1;i){dp[i][0]0;}for(int i0;inums2Size1;i){dp[0][i]0;}int res0;for(int i1;inums1Size1;i){for(int j1;jnums2Size1;j){if(nums1[i-1]nums2[j-1]){dp[i][j]dp[i-1][j-1]1;}else{dp[i][j]0;}resfmax(res,dp[i][j]);}}return res;}题目总结
dp[i][j] 以下标i - 1为结尾的A和以下标j - 1为结尾的B最长重复子数组长度为dp[i][j]。。
