partition2

题目描述

给定序列 $A[1...n]$，将序列中的元素分为前后2部分（每部分必须连续，可以为空），然后2部分分别统计总和$sum1,sum2$。

请你求出 $sum1 - sum2$ 的最大值。

输入格式

第一行包含1个整数 $n$，代表序列长度

第二行包含 $n$ 个整数 $A[i]$

输出格式

1个整数，代表 $sum1 - sum2$ 的最大值

样例 #1

样例输入 #1

3
1 0 -2

样例输出 #1

3

样例 #2

样例输入 #2

6
16 23 16 15 42 8

样例输出 #2

120

样例 #3

样例输入 #3

5
3 4 -3 2 -1

样例输出 #3

9

提示

样例3说明：$sum1 = 3+4 = 7， sum2 = -3+2-1 = -2$

数据范围：

$n\le 1000000，A[i]$ 为int范围

#include <bits/stdc++.h>
using namespace std;
#define int long long
long long n,shu[1000010],qzh[1000010],ans=-163478565912634789;
signed main(){
	cin>>n;
	for(int i=0;i<=n;i++){
		cin>>shu[i];
		qzh[i]=qzh[i-1]+shu[i];
	}
	for(int i=0;i<=n;i++){
		ans=max(qzh[i]-(qzh[n]-qzh[i]),ans);
	}
	cout<<ans;
	return 0;
}