joj1995

 1995: Energy

Result	TIME Limit	MEMORY Limit	Run Times	AC Times	JUDGE
	3s	10240K	1336	351	Standard

Mr. Jojer is a very famous chemist. He is doing a research about behavior of a group of atoms. Atoms may have different energy and energy can be positive or negative or zero, e.g. 18 or -9. Absolute value of energy can not be more than 100. Any number of continuous atoms can form an atom-group. Energy of an atom-group is defined by the sum of energy of all the atoms in the group. All the atoms form an atom-community which is a line formed by all the atoms one by one. Energy of an atom-community is defined by the greatest energy of an atom-group that can be formed by atoms in the atom-community. The problem is, given an atom-community, to calculate its energy.

Input

The input contains several test cases. Each test case consists of two lines describing an atom-community. The first line of each test case contains an integer N(N<=1000000), the number of atoms in the atom-community. The second line of each test case contains N integers, separated by spaces, each representing energy of an atom, given in the order according to the atom-community. The last test case marks by N=-1, which you should not proceed.

Output

For each test case(atom-community description), print a single line containing the energy.

Sample Input

5
8 0 6 4 -1
-1      

Sample Output

18      

This problem is used for contest: 3  163 

Submit / Problem List / Status / Discuss

#include<iostream>

using namespace std;

int s[1000000+100];

int a[1000000+100];

int main()

{

    int n;

    while(cin>>n)

    {

        if(n==-1)break;

        for(int i=0;i<n;i++)

            cin>>a[i];

        s[0]=a[0];

        for(int i=1;i<n;i++)

        {

            if(s[i-1]<0||s[i-1]+a[i]<=0)

                s[i]=a[i];

            else s[i]=s[i-1]+a[i];

        }

        int max=s[0];

        for(int i=1;i<n;i++)

        {

            if(max<s[i])

                max=s[i];

        }

        cout<<max<<endl;

    }

    return 0;

}

這個是一個動态規劃的題目當是s[i-1]<0或者s[i-1]+a[i]<=0的時候前i項的最大值就是啊a[i]，将其賦給s[i]。