讨论/算法和数据结构/求助一个问题 关于最长有序列/
求助一个问题 关于最长有序列

【问题】设计一个C/C++函数,通过对数组int a[n]进行一次扫描(即程序中只用一次循环处理),找出其中最长的有序段,即从a[j]到a[k]是有序的(注:升序或降序都是有序)且k-j+1最大。如果最长有序段不止一个,只需找出其中的一个。这里,假定n足够大,且相邻元素均不相等。
【个人思路】
1.如果只考虑升序或者降序,很好解决-->>但是同时处理升序和降序实现不了...

for(int i=0;i<nums.length-1;i++) {
    if(nums[i+1] > nums[i]) {
        count++;
    } else {  
        count = 1;
    }
    ans = count > ans ? count : ans;
}

2.难道要用动态规划?不会吧...

请各位大佬指点指点 感谢

展开讨论
共 1 个讨论

统计升序和统计降序又不冲突,按你思路可以一次遍历用两个变量分别统计上下。
其实直接找峰和谷就行了,每次计算相邻峰和谷的距离,更新最大距离即可。

int maxOrdered(vector<int> &nums) {
    int n = nums.size();
    if (n <= 1) return n;
    int ans = 1, p = 0;
    for (int i = 1; i < n-1; i++) {
        if ((nums[i] > nums[i-1] && nums[i] > nums[i+1]) || (nums[i] < nums[i-1] && nums[i] < nums[i+1])) {
            ans = max(ans, i - p + 1);
            p = i;
        }
    }
    ans = max(ans, n - p);
    return ans;
}

如果要返回该最长序列,在找到更大ans时顺便记录一下i和p即可,不改代码了。