建管家企业网站,华为手机网络营销方式,做网站的工作好吗,seo内容优化是什么文章目录1. 题目2. 解题1. 题目
https://tianchi.aliyun.com/oj/118289365933779217/122647324212270018 描述#xff1a;
给你一个长度为 n 的序列#xff0c;在他的子序列中让你找一个山谷序列#xff0c;山谷序列定义为#xff1a;
序列的长度为偶数。假设子序列的长…
文章目录1. 题目2. 解题1. 题目
https://tianchi.aliyun.com/oj/118289365933779217/122647324212270018 描述
给你一个长度为 n 的序列在他的子序列中让你找一个山谷序列山谷序列定义为
序列的长度为偶数。假设子序列的长度为 2n 。则前 n 个数是严格递减的后 n 个数是严格递增的并且第一段的最后一个元素和第二段的第一个元素相同也是这段序列中的最小值。
现在想让你找所有子序列中满足山谷序列规则的最长的长度为多少
示例
样例 1:输入: num [5,4,3,2,1,2,3,4,5]输出: 8样例解释: 最长山谷序列为[5,4,3,2,2,3,4,5]样例 2:输入: num [1,2,3,4,5]输出: 0样例解释: 不存在山谷序列2. 解题
class Solution {
public:/*** param num: sequence* return: The longest valley sequence*/int valley(vectorint num) {// write your code hereint n num.size();if(n 1) return 0;vectorint up(n, 1), down(n, 1);//最长递增/递减数组for(int i 1, j; i n; i) //正序{for(j 0; j i; j){if(num[j] num[i])//前面的比当前大递减down[i] max(down[i], down[j] 1);}}for(int i n-2, j; i 0; i--) //逆序遍历{for(j i1; j n; j){if(num[j] num[i])//后面的比当前大递增up[i] max(up[i], up[j] 1);}}int maxlen 0;for(int i 0, j; i n; i){for(j i1; j n; j){if(num[i] num[j])//最小的数{maxlen max(maxlen, min(down[i],up[j])*2);} // 两侧等长的递减 递增}}return maxlen;}
};时间复杂度 O(n2)O(n^2)O(n2) 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
