求数组中最大子数组的和02

 1 //返回一个整数数组中最大子数组的和
 2 //有正数、有负数、数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和、将数组首尾相连、返回最大子数组的位置
 3 //张哲、张晓菲 2016/3/22
 4 
 5 #include<iostream>
 6 using namespace std;
 7 #define N 10000
 8 
 9 int main()
10 {
11     int num,arr[N];
12     int sum=0;
13     cout<<"请输入数组元素个数：";
14     cin>>num;
15     cout<<"请输入数组元素的值：";
16     for(int i=0;i<num;i++)//输入环状数组的元素值
17     {
18         cin>>arr[i];
19     }
20     for(int i=num;i<(2*num-1);i++)//将环抻直，例如环状数组值原先为[A,B,C,D],那么抻直之后为[A,B,C,D,A,B,C]
21     {
22         arr[i]=arr[i%num];
23     }
24     cout<<"环抻直之后的数组相当于："<<endl;
25     for(int i=0;i<(2*num-1);i++)
26     {
27         cout<<arr[i]<<" ";
28     }
29     cout<<endl;
30 
31     int max=arr[0];
32     int end,start,cstart;//end为结束位置 start为起始位置
33 
34     //求子数组最大和
35     for(int j=0;j<num;j++)
36     {
37         sum=0;
38         for(int i=j;i<j+num;i++)
39         {
40             if(sum<=0)
41             {
42                 sum=arr[i];
43                 cstart=i;//当前最大子数组的起始位置
44             }
45             else
46                 sum=sum+arr[i];
47             if(sum>max)
48             {
49                 max=sum;
50                 start=cstart;
51                 end=i;
52              }
53         }
54     }
55 
56     cout<<"子数组和的最大值为："<<max<<endl;
57     cout<<"最大子数组的起始位置为环抻直后的第"<<start+1<<"个元素，结束位置为环抻直后的第"<<end+1<<"个元素。"<<endl;
58     return 0;
59 }