#include<iostream>
2 #include<string>
3 #include<ctime>
5 #define N 5
6 using namespace std;
7
8 int MaxSum(int *arr, int size)
9 {
10 int i, sum, max1, max2, dp,min;
11 dp = max1 = arr[0];
12 for (i = 1; i < size; ++i)//非环形数组;++i,先i自加1，再使用i的值
13 {
14 if (dp < 0)
15 dp = arr[i];
16 else
17 dp += arr[i];
18 if (dp > max1)
19 max1 = dp;
20 }
21 sum = min = dp = arr[0];
22 for (i = 1; i < size; ++i)//求数组最小子数组和，再用数组全部元素和减去，则结果跨过arr[n-1]到arr[0]
23 {
24 if (dp>0)
25 dp = arr[i];
26 else
27 dp += arr[i];
28 if (dp < min)
29 min = dp;
30 sum += arr[i];
31 }
32 max2 = sum - min;//数组全部元素和减去最小子数组
33 return max1>max2 ? max1 : max2;//三目运算符；如果max1>max2,将max1的值返回，否则返回max2
34 }
35 int main()
36 {
37 int arr[N];
38 srand(time(0));
39 cout << "随机数组为：" << endl;
40 for (int j = 0; j < N ; j++)
41 {
42 arr[j] = rand() % 20 - 10;
43 cout << arr[j] << " ";
44 }
45 cout << endl;
46 cout << "最大子数组的和为：" << MaxSum(arr, N) << endl;
47 return 0;
48 }
思想将一位数组编程成一个环，将数组累加一遍，然后把第一位数放在最后一位在累加 最后比较大小