摘要：
1050循环数组的最大子段和基准时间限制：1秒空间限制：131072KB得分：10难度：2级算法问题关注由N个整数组成的循环序列a[1]、a[2]、a[3]、…+a[j]的连续子段之和的最大值。当所有整数都为负时，总和为0。输入行1：整数序列的长度N行2-N+1：N个整数输出循环数组的子段的最大总和。输入示例6-211-413-5-2输出示例20与上一主题类似，但有一个循环……首先，直接计算整个序列的最大子串和，然后将所有序列取相反的数字，然后减去和得到最大子串总和，然后取较大的值。
基准时间限制：1 秒 空间限制：131072 KB 分值: 10 难度：2级算法题
收藏
关注N个整数组成的循环序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续的子段和的最大值（循环序列是指n个数围成一个圈，因此需要考虑a[n-1],a[n],a[1],a[2]这样的序列）。当所给的整数均为负数时和为0。
例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。
Input
第1行：整数序列的长度N（2 <= N <= 50000) 第2 - N+1行：N个整数 (-10^9 <= S[i] <= 10^9)
Output
输出循环数组的最大子段和。
Input示例
6 -2 11 -4 13 -5 -2
Output示例
20
和上道题目类似,然而有循环的存在....先直接求一下整个序列的最大子串和然后把序列全部取相反数再求一下用sum减去就是最大子串和，然后取较大值。
代码:
1 #include <vector> 2 #include <map> 3 #include <set> 4 #include <algorithm> 5 #include <iostream> 6 #include <cstdio> 7 #include <cmath> 8 #include <cstdlib> 9 #include <string> 10 #include <cstring> 11 #include <queue> 12 #include <stack> 13 using namespace std; 14 15 long long dp[55555],a[55555]; 16 17 long long solve(int n,long long dp[]) 18 { 19 long long ans=0,b=0; 20 for(int i=0; i<n; i++){ 21 if(b>=0){ 22 b+=dp[i]; 23 } 24 else{ 25 b=dp[i]; 26 } 27 if(b>ans){ 28 ans=b; 29 } 30 } 31 return ans; 32 } 33 34 int main() 35 { 36 int n; 37 scanf("%d",&n); 38 long long sum=0; 39 memset(dp,0,sizeof(dp)); 40 for(int i=0; i<n; i++){ 41 scanf("%lld",&dp[i]); 42 sum+=dp[i]; 43 a[i]=-dp[i]; 44 } 45 long long p=solve(n,dp); 46 long long q=solve(n,a); 47 long long m=max(p,sum-q); 48 printf("%lld ",m); 49 }