题目分析
最长上升子序列(Longest Increasing Subsequence, LIS):这是非常有趣的一个题目,也是笔试面试常常出现的一道数组题,这道题目小伙伴们必须要掌握动态规划的解法,但是能否想到更加巧妙的方法呢?
容器是C++非常方便的功能,今天给小伙伴们介绍stack和queue库,一个是栈,一个是队列,在数据结构中这两个内容也是必须掌握的重点内容,在刷题时也常常使用它们,因此在一篇博客中将它们放在一起介绍。
这个题目和前两天说的一个最大子序和的题目类似,不过这个题目不是求和而是求积。求和和求积有什么区别呢?为啥这个题目的难度就是中等,而上一个题目的难度是简单呢。求和的题目不会涉及到符号的问题,如果前缀和小于0,则相加时不考虑前缀,这时上一个题目的核心思想。而这个题目的难点在于,可能出现负数乘负数产生正数的情况。
从今天开始进入另一个有趣的部分——子序列相关题目,这是笔试面试中最最经典的问题之一,常用的解法是动态规划,小伙伴们一定要留心这类题目。虽然看起来难度并不大,但是遇到时可能会出现眼高手低的情况。