LeetCode·674.最长连续递增序列·动态规划
2023-09-27 14:26:29 时间
链接:https://leetcode.cn/problems/longest-continuous-increasing-subsequence/solution/-by-xun-ge-v-b5ck/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
题目
示例
思路
小知识 memset每次只能对一个字节的单位赋值,所以当用memset个int型数赋 1 时,实际赋为 00000001 00000001 00000001 00000001
- 确定dp数组(dp table)以及下标的含义
dp[i]:以下标i为结尾的数组的连续递增的子序列长度为dp[i]。
注意这里的定义,一定是以下标i为结尾,并不是说一定以下标0为起始位置。
- 确定递推公式
如果 nums[i + 1] > nums[i],那么以 i+1 为结尾的数组的连续递增的子序列长度 一定等于 以i为结尾的数组的连续递增的子序列长度 + 1 。
即:dp[i + 1] = dp[i] + 1;
因为本题要求连续递增子序列,所以就必要比较nums[i + 1]与nums[i],而不用去比较nums[j]与nums[i] (j是在0到i之间遍历)。
既然不用j了,那么也不用两层for循环,本题一层for循环就行,比较nums[i + 1] 和 nums[i]。
这里大家要好好体会一下!
- dp数组如何初始化
以下标i为结尾的数组的连续递增的子序列长度最少也应该是1,即就是nums[i]这一个元素。
所以dp[i]应该初始1;
- 确定遍历顺序
从递推公式上可以看出, dp[i + 1]依赖dp[i],所以一定是从前向后遍历。
代码
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int findLengthOfLCIS(int* nums, int numsSize){
int dp[numsSize];
dp[0] = 1;
int max = 1;
for(int i = 1; i < numsSize; i++)
{
dp[i] = 1;
if(nums[i] > nums[i-1])
dp[i] = dp[i-1] + 1;
max = MAX(max, dp[i]);
}
return max;
}
作者:xun-ge-v
链接:https://leetcode.cn/problems/longest-continuous-increasing-subsequence/solution/-by-xun-ge-v-b5ck/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
相关文章
- LeetCode Anagrams My solution
- LeetCode高频题33. 搜索旋转排序数组
- 【Leetcode】1143. 最长公共子序列(中等)
- [LeetCode] Distinct Subsequences
- [LeetCode]392. 判断子序列
- 【Java数据结构与算法】LeetCode 0206. 反转链表的三种Java实现方法
- LeetCode数据结构_C语言题解系列-串
- 179、【动态规划】leetcode ——115. 不同的子序列(C++版本)
- 128、【贪心算法】leetcode ——376. 摆动序列(C++版本)
- 【LeetCode】67. Add Binary
- LeetCode: Linked List Cycle [141]
- 【leetcode】106: 从中序与后序遍历序列构造二叉树
- [LeetCode] 1218. Longest Arithmetic Subsequence of Given Difference 最长定差子序列
- [LeetCode] 1203. Sort Items by Groups Respecting Dependencies 项目管理
- [LeetCode] 1092. Shortest Common Supersequence 最短公共超序列
- [LeetCode] Split Array into Fibonacci Sequence 分割数组成斐波那契序列
- [LeetCode] Arithmetic Slices II - Subsequence 算数切片之二 - 子序列
- [LeetCode] Random Pick Index 随机拾取序列
- [LeetCode] 267. Palindrome Permutation II 回文全排列之二
- [LeetCode] 298. Binary Tree Longest Consecutive Sequence 二叉树最长连续序列
- [LeetCode] 187. Repeated DNA Sequences 求重复的DNA序列
- leetcode算法144.二叉树的前序遍历