Question E: sequence game

Time limit: 1.000 Sec memory limit: 128 MB
Submit state

Title Description

Xiao Ming is playing a series summation game recently in order to exercise his intelligence. Let the length of the sequence be n, and each number is an integer within the range of [- 1000], that is, the range is - 1000 ~ 1000.
Rules of the game: Xiao Ming can choose a continuous substring of any length from this sequence and sum it. Xiao Ming wants to know the maximum value of substring and absolute value. Can you help him?
Absolute value: the absolute value of a positive number is itself, and the absolute value of a negative number is its opposite.
For example, the absolute value of 5 is 5 and the absolute value of - 7 is 7.

input

There are two lines for input. The first line is an integer n, and the second line is an integer n.

output

Output a number, which is the maximum value of the substring and absolute value of the sequence.

Sample input: Copy

[input example 1]
10
-562 232 969 201 -111 378 -610 127 245 932

[input example 2]
10
868 -838 -958 200 867 -920 -493 114 -800 757

[input example 3]
10
-607 -260 -270 -833 560 -280 404 -542 560 -115

Sample output: Copy

[output example 1]
2363

[output example 2]
2828

[output example 3]
1970

Tips

[example explanation]
For example 1, it can be found that 232 + 969 + 201-111 + 378-610 + 127 + 245 + 932 = 2363, so 2363 is the maximum absolute value.
For example 2, it can be found that - 838 + - 958 + 200 + 867 + - 920 + - 493 + 114 + - 800 = - 2828, so 2828 is the maximum absolute value.


[data scale]
For 20% data, n < = 10
For 50% of the data, n < = 100 is satisfied
For 70% of the data, n < = 1000 is satisfied
For 100% data, n < = 1000000

#include<iostream>
using namespace std;
const int N =1e6+10;
int max_1[N],min_1[N],fresh[N],sum[N];
int main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&fresh[i]);
		sum[i]=sum[i-1]+fresh[i];
	}
	int  ans=0;
	int mina=0;int maxa=0;
	for(int i=1;i<=n;i++)
	{
		//mina=min(fresh[i],mina);
		mina=min(sum[i],mina);
		//maxa=max(fresh[i],maxa);
		maxa=max(sum[i],maxa);
		ans=max(ans,abs(maxa-mina));
	}
	cout<<ans;
}

 

7-1 maximum subsets and problems (20 points)

Given the sequence {N1, N2,..., NK} composed of K integers, "continuous sub column" is defined as {Ni, Ni+1,..., Nj}, where {1 ≤ i ≤ j ≤ K. "Maximum child column sum" is defined as the largest sum of all consecutive child column elements. For example, given the sequence {- 2, 11, - 4, 13, - 5, - 2}, its continuous sub columns {11, - 4, 13} have the largest sum of 20. Now you are required to write a program to calculate the maximum sub column sum of a given integer sequence.

The purpose of this question is to test the performance of various algorithms under various data conditions. The characteristics of test data of each group are as follows:

• Data 1: equivalent to the sample to test the basic correctness;
• Data 2: 102 random integers;
• Data 3: 103 random integers;
• Data 4: 104 random integers;
• Data 5: 105 random integers;

Input format:

Enter the integer in line k (≤ 100000); Line 2 gives K integers separated by spaces.

Output format:

Outputs the maximum child column sum in a row. If all integers in the sequence are negative, 0 is output.

Input sample:

6
-2 11 -4 13 -5 -2

Output example:

20

#include<iostream>
using namespace std;
const int N = 1e5+10;
#define ll long long
ll a[N];
ll b[N];
ll maxa=0,mina=0x3f3f3f3f;
int main()
{
    int n;cin>>n;
    int t=0;
    for(int i=1;i<=n;i++){cin>>a[i];if(a[i]>=0)t=1;}
    if(t==0){cout<<"0";return 0;}
    for(int i=1;i<=n;i++)b[i]=b[i-1]+a[i];
    ll maxaa=0;
    for(int i=1;i<=n;i++)
    {
        maxa=max(maxa,b[i]);
        mina=min(mina,b[i]);
        maxaa=max(maxaa,maxa);
        maxaa=max(maxaa,b[i]-mina);
     }
    for(int i=1;i<=n;i++)
    {
        maxaa=max(maxaa,a[i]);
    }
    cout<<maxaa;
}

Use prefix sum to find the difference between the longest and shortest sequence in the current state