Input示例
6-211-413-5-2
Output示例
20
分析:
有两种可能,第一种为正常从[1 - n]序列中的最大子字段和;第二种为数组的total_sum - ([1-n]序列中的最短序列和)
最后结果为 max { 第一种, 第二种}。
对于第二种:
循环数组求最大子段和,可能出现中间的一部分不要,要两边的数。比如:-1 4 -1 -5 5 -2 1 -1 3,他的最大子段和就为 左边的-1 4加上右边的5 -2 1 -1 3,也就是,去掉1 -5这一段后的结果。而-1 -5这一段其实是最小字段和(序列总和一定,总和 - 最大子段和 = 最小子段和)
#include "iostream"#include "cstdio"using namespace std;#define LL long long#define N 50010int arr[N];int main(){ int n; LL sum,sum01,sum02; while(~scanf("%d",&n)){ sum=0;sum01=0;sum02=0; for(int i=0;i