Four Segments

时间: 1ms        内存:128M

描述:

您将获得一个包含n个整数的数组。设sumlr)是区间[l,r)位置上所有数字的总和(计算第l个元素,不计算第r个元素)。0l≤r≤n。数组中的索引从0开始编号。

 

例如,如果a = [-5,3,9,4],则sum0,1= -5sum0,2= -2sum1,4= 16

 

选择三个界限符delim0delim1delim20delim0delim1≤delim2≤n)和以这样的方式划分阵列的值res = sum(0, delim0) – sum(delim0, delim1) + sum(delim1, delim2) – sum(delim2, n)res的值最大。

输入:

第一行包含一个整数n1n≤5000.

第二行包含n号码一个a0, a1, …, an-1 (-10^9ai10^9).

输出:

选择三个界限符,使res的值最大。如果有多个答案,请打印字典序最小的

示例输入:

3
-1 2 3

示例输出:

0 1 3

提示:

参考答案(内存最优[1120]):

#include<stdio.h>
long long int  ans=-1e9;
using namespace std;
int main()
{
    int i,j,k;
    long long int a[5010];
    a[0]=0;
    int n,m,t;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&t);
        a[i]=a[i-1]+t;
    }
    int t1,t2;
    int d1,d2,d3;
    for(j=0;j<=n;j++)
    {
        t1=0;
        for(i=0;i<=j;i++)
        {
            if(a[i]>a[t1])
            {
                t1=i;
            }
        }
        t2=j;
        for(k=j;k<=n;k++)
        {
            if(a[k]>a[t2])
            {
                t2=k;
            }
        }
        if(a[t1]+a[t2]-a[j]>ans)
        {
            ans=a[t1]+a[t2]-a[j];
            d1=t1;
            d2=j;
            d3=t2;
        }
    }
    printf("%d %d %d",d1,d2,d3);
    return 0;
}

参考答案(时间最优[7]):

#include<bits/stdc++.h>
#define fin             freopen("in.txt","r",stdin)
typedef long long ll;
using namespace std;
const int maxn = 5005;
int a[maxn],l[maxn],r[maxn],x,y,z;
ll sum[maxn],ans=-0x3f3f3f3f;
int main() {
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i], sum[i]=sum[i-1]+a[i];
    for (int i=1;i<=n;i++) {
        if (sum[i]>sum[ l[i-1] ]) l[i]=i;
        else l[i]=l[i-1];
    }
    r[n]=n;
    for (int i=n-1;i>=0;i--) {
        if (sum[i]>=sum[ r[i+1] ]) r[i]=i;
        else r[i]=r[i+1];
    }
    for (int i=0;i<=n;i++)
        if(sum[l[i]]-sum[i]+sum[r[i]]>ans) {
            ans=sum[l[i]]-sum[i]+sum[r[i]];
            x=l[i],y=i,z=r[i]; 
        }
    cout<<x<<" "<<y<<" "<<z<<endl;
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。