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

浏览数：48 / 时间：2015年06月08日

要求：

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

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

如果数组A[0]……A[j-1]首尾相邻，允许A[i-1]， …… A[n-1]， A[0]……A[j-1]之和最大。

同时返回最大子数组的位置。

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

思路：

结对开发:张子超马思勉

刚看到这个题目首先想到的是将随机产生的数组复制一遍放在原数组后面，然后再进行求解，后来在和马思勉的探讨中得到新的解决思路，首先按照求解整数数组方法，求解最大子数组的和，然后将第一个数放在最后一个数后面，形成一个新的数组，继续进行求解，而这就需要定义长为两倍数组的一个整数组，每求出一个和将第一个数放最后。在实际敲代码过程中，求出的最大子数组的和远远大于正确的值，与预期不符。因此从网上寻找思路，发现一种更加简单的思路，将求环的方法转化成求一个非环形，即求出最小子数组的和，然后用整个数组的和减去最小子数组的和，得到的肯定是最大的子数组和。代码如下：

 1 #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 }