写个算法解决下述问题:给一组连续的温度 T: t1,t2,t3,....,tn,当且仅当满足t1<t2>t3<t4>t5<t6.....或t1>t2<t3>t4<t5>t6....的时候,我们说T是一个波动的温度序列。现在给出一个温度序列,返回作为波动温度序列的最长子序列的长度。通过从原始序列中删除一些(也可以不删除)元素来获得子序列,剩下的元素保持其原始顺序。
时间: 2023-06-08 11:04:33 浏览: 173
好的,这是一个算法问题。根据题目描述,我们可以发现只有当相邻两个数的大小关系出现了反转(变小或变大)时,这个序列才是一个波动温度序列。因此我们可以用动态规划来解决这个问题。设dp[i][0]为以第i个数结尾且是下降趋势的最长波动子序列长度,dp[i][1]为以第i个数结尾且是上升趋势的最长波动子序列长度。初始化所有的dp[i][0]和dp[i][1]都为1。接着,对于第i个数,我们需要遍历它前面的所有数,如果满足该数与前一个数大小关系出现了反转(即满足波动温度序列的性质),则可以更新dp[i][0]和dp[i][1]。最后我们只需要返回dp数组中的最大值即可。
阅读全文