qq_41094461
qq_41094461
采纳率100%
2017-11-18 06:34

编程题目,哪位大神教我做,谢谢!

已采纳

Problem Description
长度为 n 的序列,把它划分成两段非空的子序列,定义权值为:两段子序列的最大值的差的绝对值。求可能的最大的权值。
数据范围:
2 <= n <= 10^6 , 0 < 序列内的数 <= 10^6 。
Input
第一行输入一个 T,表示有 T 组数据。
接下来有 T 组数据,每组数据的第一行输入一个数 n ,第二行输入 n 个数。
Output
每组数据输出可能的最大的权值。
Sample Input
1
3
1 2 3
Sample Output
2

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

3条回答

  • caozhy 回答这么多问题就耍赖把我的积分一笔勾销了 4年前
     #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int N = 1e6+10;
    int a[N], pre[N], sum[N];
    int main() {
        int T;
        cin>> T;
        while(T--) {
            int n;
            cin >> n;
            memset(sum, 0, sizeof(sum));
            memset(pre, 0, sizeof(pre));
            for(int i = 1; i <= n; i ++) cin >> a[i];
            for(int i = 1; i <= n; i ++) {
                sum[i] = max(sum[i-1], a[i]);
            }
            for(int i = n; i > 0; i --) {
                pre[i] = max(pre[i+1], a[i]);
            }
            int MAX = -1;
            for(int i = 2; i <= n; i ++){
                MAX = max(MAX, abs(pre[i]-sum[i-1]));
            }
            printf("%d\n",MAX);
        }
        return 0;
    }
    
    点赞 1 评论 复制链接分享
  • er111er zjloijr 4年前

    这道题很容易想到枚举中间点,然后找两段序列的最大值,但是这样做的时间复杂度为O(n^2),规定时限1s可能无法完成,首先我们枚举i,i在枚举时,可以顺便更新最大值,从而在O(n)时间找出序列a[1, i-1]的最大值,而至于序列a[i, n]的最大值,我们可以设一个p[i]表示序列a[i, n]的最大值,倒序枚举i,就可以在O(n)时间处理a[i,n]的最大值。然后就可以O(n)枚举,O(1)求权值,也就不会超时了。

    点赞 1 评论 复制链接分享
  • Runner__1 T_world 4年前

    感觉直接求这个序列中的最大值减去最小值的绝对值就可以了

    点赞 1 评论 复制链接分享

为你推荐