一维数组首尾相连

一.题目

返回一个整数数组中最大子数组的和

二.要求

输入一个整形数组，数组里有正数也有负数。

数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。

如果数组A[0]……A[j-1]首尾相邻，允许A[i-1]， …… A[n-1]， A[0]……A[j-1]之和最大。同时返回最大子数组的位置。

求所有子数组的和的最大值。要求时间复杂度为O(n)

三，代码

 1 #include <iostream>
 2 #define N 1000
 3 using namespace std;
 4 
 5 int main ()
 6 {
 7     int a[N],n;
 8     int sum,max;
 9     int begin,last;
10     int i,j,t,k;
11     char status = 'y';
12 
13     while(status == 'Y' || status == 'y')
14     {
15 
16         cout<<"请输入数组长度n:"<<endl;
17         cin>>n;
18     
19         cout<<"请输入"<<n<<"个数:"<<endl;
20         for (i=0; i<n; i++)
21         {
22             cin>>a[i];
23         }
24 
25         //初始化
26         begin = 0;
27         last = 0;
28         max = 0; 
29 
30         for (i=0; i<n; i++)
31        {
32             sum = 0;
33 
34             for (j=i; j<n; j++)
35             {
36                 sum += a[j];
37                  
38                 if ( sum > max )
39                 {
40                     max = sum;
41                     begin = i;
42                     last = j;
43                 }
44             }
45          
46             for(k=0; k<i; k++)
47             {
48                 sum += a[k];
49 
50                 if ( sum > max )
51                 {
52                    max = sum;
53                    begin=i;
54                    last = k;
55                 }
56             }
57         }
58 
59         cout<<"最大子数组之和为:"<<endl;
60         cout<<max<<endl;
61 
62         cout<<"最大子数组序列为："<<endl;
63 
64         //当最大子数组出现在首尾相接的情况下
65         if ( last < begin)
66         {
67             for (i=begin; i<n; i++)
68             {
69                 cout<<a[i]<<" ";
70             }
71             for (i=0; i<=last; i++)
72             {
73                 cout<<a[i]<<" ";
74             }
75             cout<<endl;
76         }
77         else
78         {
79             for (i=begin; i<=last; i++)
80             {
81                 cout<<a[i]<<" ";
82             }
83             cout<<endl;
84         }
85 
86         cout<<endl;
87         cout<<"是否继续(是输入y或Y,否输入n或N)："<<endl;
88         cin>>status;
89     }
90 
91     return 0;
92 }

在这里设定变量的时候，首先就要记得需要初始化，在这里我把情况设定为两种情况，一种是最大值不在首尾相接时，另一种是在首尾相接时，通过两个循环，第一次是一个为头，另一个紧跟着循环，通过一次次的比较，当找到最大值时，又通过循环输出数值就好了。

小组成员：郑成，洪烨，张一然