蚂蚁的难题(二)

时间限制：

1000 ms  |  内存限制：65535 KB

难度：

3

描述

下雨了，下雨了，蚂蚁搬家了。

已知有n种食材需要搬走，这些食材从1到n依次排成了一个圈。小蚂蚁对每种食材都有一个喜爱程度值Vi，当然，如果Vi小于0的时候，表示蚂蚁讨厌 这种食材。因为马上就要下雨了，所以蚂蚁只能搬一次，但是能够搬走连续一段的食材。时间紧急，你快帮帮小蚂蚁吧，让它搬走的食材喜爱值和最大。

输入

有多组测试数据（以EOF结尾）。

每组数据有两行，第一行有一个n，表示有n种食材排成了一个圈。（1 <= n<= 50000)

第二行分别有n个数，代表蚂蚁对第n种食材的喜爱值Vi。(-10^9 <= Vi <= 10^9)

输出

输出小蚂蚁能够搬走的食材的喜爱值总和的最大。

样例输入

33 -1 25-8 5 -1 3 -9

样例输出

57

这题是最大字段和的变形，关键的地方是数据可以循环，分两步解决：

第一步，求出这组数据的首尾不循环的最大字段和s1

第二步，这个可以在第一步的时候，求出他的最小字段和s2,还有全部数据之和s,那么，根据题目的要求，将s1与s-s2的值比较就可以得到最后的结果。

1 #include
       
         2 #define MAX(x,y) x>y?x:y 3 #define MIN(x,y) x>y?y:x 4 long long arr[200001]; 5 int main(){
     long long n,temp1,max,min,s,temp2,result; 6 while(~scanf("%lld",&n)){ 7     for(int i=0;i
        
         arr[i])temp2=arr[i];15         else temp2+=arr[i];16         min=MIN(min,temp2);17         s+=arr[i];18     //    printf("t=%d temp=%d\n",t,temp);19         result=MAX(s-min,max);20     }21     if(result<0)result=0;22     printf("%lld\n",result);}23     return 0;24 }
        
       

 

首尾相连数组的最大子数组和

时间限制：

1000 ms  |  内存限制：65535 KB

难度：

4

描述

给定一个由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 两题代码一样。。。