返回数组中最大子数组的和

 1 #include "stdafx.h"
 2 int _tmain(int argc, _TCHAR* argv[])
 3 {
 4     return 0;
 5 }
 6 #include
 7 using namespace std;
 8 int maxSum(int* a, int n)  //定义一个求一维数组的最大子数组和的方法
 9 {
10     int sum = 0;
11 
12     int b = 0;
13 
14     for (int i = 0; i)
15     {
16         if (b<0)
17             b = a[i];
18         else
19             b += a[i];
20         if (sum<b)
21             sum = b;
22     }
23     return sum;
24 }
25 
26 int main()
27 {
28     int n, temp, b;
29     int  sum = 0;
30     int i;
31     int a1, a2;
32     cout <<"请输入数组长度： " << endl;
33     cin >> n;
34     cout <<"请输入数组的每个元素(空格隔开)： " << endl;
35     int *a = new int[n];
36 
37     for (i = 0; i)
38     {
39         cin >> a[i];
40     }
41     cout <<"此首尾相连的数组中最大子数组的和有以下几种情况：" << endl;
42     cout <<"第1种方式：" << endl;
43     for (i = 0; i)
44     {
45         cout <"  ";
46     }
47     cout <<"所求最大子数组和为：" < endl;
48     a1 = maxSum(a, n);
49     for (b = 1; b)
50     {
51         temp = a[0];
52         for (i = 1; i <= n; i++)
53         {
54             a[i - 1] = a[i];
55 
56         }
57         a[n - 1] = temp;
58         cout <<"第" <1 <<"种方式：" << endl;
59         for (i = 0; i)
60         {
61             cout <"  ";
62         }
63         cout <<"最大子数组和为：" < endl;
64         if (maxSum(a, n) >= sum)
65         {
66             sum = maxSum(a, n);
67         }
68     }
69     a2 = sum;
70     cout << endl;
71     if (a1 >= a2)
72     {
73         cout <<"综上所述，最大的子数组和为：" < endl;
74     }
75     else
76     {
77         cout <<"综上所述，最大的子数组和为：" < endl;
78     }
79     system("pause");
80     return 0;    
81 }