题目:返回一个整数数组中最大子数组的和。（要求程序必须能处理1000 个元素）

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

1、题目:返回一个整数数组中最大子数组的和。

2、要求：

　　要求程序必须能处理1000 个元素；

　　每个元素是int32 类型的；

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

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

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

3、设计思路：

　　将数组大小定义为1000，对于每个元素定义为int32类型，我们取数的时候对其进行了乘4294967296，使数组内的元素可以越界。

4、程序代码：

 1 #include <iostream>
 2 #include<stdlib.h>
 3 #include<time.h>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int i;
 9     int a[10000];
10     int max = 0;
11     int b = 0;
12 
13     srand(time(NULL));
14     cout<<"数组为："<<endl;
15     for (i = 0; i<10000; i++)
16     {
17         a[i] = rand()*4294967296 ;
18     }
19     for (i = 0; i<10000; i++)
20     {
21         cout << a[i] << ‘\t‘;
22     }
23     cout << endl;
24 
25     for (i = 0; i < 10000; i++)
26     {
27         b += a[i];
28         if (b < 0)
29             b = 0;
30         if (b > max)
31             max = b;
32     }
33     if (max == 0)
34     {
35         max = a[0];
36         for (i = 0; i < 10000; i++)
37         {
38             if (max < a[i])
39             {
40                 max = a[i];
41             }
42         }    
43     }
44     cout <<"最大子数组为："<< max << endl;
45     system("pause");
46     return 0;
47 }