第2章 Android应用的界面编程

Maximum sum
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 31468   Accepted: 9665

Description

Given a set of n integers: A={a1, a2,..., an}, we define a function d(A) as below:
Your task is to calculate d(A).

Input

The input consists of T(<=30) test cases. The number of test cases (T) is given in the first line of the input. 
Each test case contains two lines. The first line is an integer n(2<=n<=50000). The second line contains n integers: a1, a2, ..., an. (|ai| <= 10000).There is an empty line after each case.

Output

Print exactly one line for each test case. The line should contain the integer d(A).

Sample Input

1

10
1 -1 2 2 3 -3 4 -4 5 -5

Sample Output

13

Hint

In the sample, we choose {2,2,3,-3,4} and {5}, then we can get the answer. 

Huge input,scanf is recommended.

Source

POJ Contest,Author:Mathematica@ZSU

题意

给你n个数字的序列。叫你找出两个连续子段。两子段不重合。使得两字段中所有数字的和最大。

思路:

开始因为没注意到不重合WA了数次!解法还是蛮简单的。从前往后和从后往前分别做一次最大子段和。然后枚举分段点。就可以得到答案了。

详细见代码:

#include<algorithm>
#include<iostream>
#include<string.h>
#include<sstream>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
//#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double PI=acos(-1.0);
const int maxn=50100;
int dpl[maxn],dpr[maxn],ml[maxn],arr[maxn];
int main()
{
    int t,n,i,ans;

    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        ans=-INF;
        dpl[0]=dpr[n+1]=ml[0]=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&arr[i]);
            dpl[i]=max(arr[i],arr[i]+dpl[i-1]);//从前往后
            ans=max(ans,dpl[i]);
            ml[i]=ans;//记录到i时的最大字段和
        }
        ans=-INF;//必须要再次初始化。开始偷懒认为死一样的。结果会导致最后只有一个字段。数据见下
        for(i=n;i>1;i--)
        {
            dpr[i]=max(arr[i],arr[i]+dpr[i+1]);
            ans=max(ans,ml[i-1]+dpr[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}
/*
1
10
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
*/


郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。