题目1527：首尾相连数组的最大子数组和
- 题目描述：
-
给定一个由N个整数元素组成的数组arr，数组中有正数也有负数，这个数组不是一般的数组，其首尾是相连的。数组中一个或多个连续元素可以组成一个子数组，其中存在这样的子数组arr[i],…arr[n-1],arr[0],…,arr[j]，现在请你这个ACM_Lover用一个最高效的方法帮忙找出所有连续子数组和的最大值（如果数组中的元素全部为负数，则最大和为0，即一个也没有选）。
- 输入：
-
输入包含多个测试用例，每个测试用例共有两行，第一行是一个整数n（1=<n<=100000），表示数组的长度，第二行依次输入n个整数（整数绝对值不大于1000）。
- 输出：
-
对于每个测试用例，请输出子数组和的最大值。
- 样例输入：
-
61 -2 3 5 -1 256 -1 5 4 -7
- 样例输出：
-
1014
- 来源：
- 思路：这个题比较好，仔细一看还是维护一个小根堆的问题，sum[i]( 前缀和)-Min(sum[k] ,i-N+1<=K<i) ,而且删除堆顶最下次操作没有影响，这种题作为公司笔试题比 较常见了，注意优先队列的写法。
-
#include
#include #include #include #include #include #include #include #include #define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))using namespace std ;const int size=100008 ;struct Me{ struct Node{ int id ; int sum ; Node(){} Node(int i ,int s):id(i),sum(s){} friend bool operator <(const Node A ,const Node B){ return A.sum>B.sum ; } }; int N ; int num[size*2] ; int sum[size*2] ; Me(){} Me(int n):N(n){} void read(){ for(int i=1;i<=N;i++){ scanf("%d",&num[i]) ; num[N+i]=num[i] ; } } int gao_qi(){ read() ; int ans=0 ; priority_queue que ; Node now ; sum[0]=0 ; for(int i=1;i<=N*2;i++){ sum[i]=sum[i-1]+num[i] ; if(i<=N) ans=Max(ans,sum[i]) ; while(!que.empty()){ now=que.top() ; if(now.id>=i-N+1){ ans=Max(sum[i]-now.sum,ans) ; break ; } que.pop() ; } que.push(Node(i,sum[i])) ; } return ans<0?0:ans; }};int main(){ int n ; while(scanf("%d",&n)!=EOF){ Me me(n) ; printf("%d\n",me.gao_qi()) ; } return 0 ;}