动态规划-最长连续递增序列

动态规划经典题型,难度低。

给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r(l < r)确定,如果对于每个 l <= i < r,都有 nums[i] < nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。

来源:力扣(LeetCode)

int findLengthOfLCIS(int* nums, int numsSize){
    int* dp=calloc(numsSize,sizeof(int));
    dp[0]=1;
    int max=1;
    for(int i=1;i<numsSize;i++)
    {
        dp[i]=1;
        if(nums[i-1]<nums[i])
            dp[i]=dp[i-1]+1;
        //printf("%d\n",dp[i]);
        if(dp[i]>max)
        max=dp[i];
    }
    return max;
}

需要注意的问题:初始化动态分配的int类型数组需要使用for循环而不是memset,否则可能会出现16843009错误。
原因:memset是按字节赋值的,取变量a的后8位二进制进行赋值,总结:memset()只有在初始化-1,0时才会正确。想要初始化为其他值需要用for循环实现。

上一篇:1304:数的划分


下一篇:NOIP 模拟七 考试总结