一组数组中最大子数组之和

思路：

1、随机输入数组

2、求出数组之和a

3、用a与数组第一个数开始做和。如果数字小于a,那么舍弃该数；如果大于a,继续计算a与第一个数与第二个数之和，如果小于a舍弃这两个数，如果大于a,继续计算a与第一个数、第二个数、第三个数之和......直到计算的最后一个数为止。

4、与第3步步骤类似，只是从最后一个数开始计算，到第一个数为止。

5、求出最大子数组，输出该字数组数字，以及之和。

源代码：

  1 //XiaoSong Du 2015/3/22
  2 #include <iostream>
  3 #include <time.h>
  4 using namespace std;
  5 #define N 10
  6 
  7 int a[N] ,b,b1,d,d1 = 0,jj = 0,k1 = 0;
  8 int maxd = 0,maxd1 = 0 ,end1 = 0,end2=0;
  9 void zheng(int& j,int k)
 10 {
 11     d = 0;
 12     for (int i = j;i <= k;i++)
 13     {
 14         d += a[i];
 15         if (d >= maxd)
 16         {
 17             maxd = d;
 18             end1 = i;
 19         }
 20         if (b - d >= b)
 21         {
 22             b = b - d; 
 23             j++;
 24             j = j + jj;
 25             d = 0;
 26             jj = 0;
 27         }
 28         else {
 29             jj++;
 30         }
 31     }
 32 }
 33 void ni(int j,int &k )
 34 {
 35     d1 = 0;
 36     for (int i = k;i >= j;i--)
 37     {
 38         d1 += a[i];
 39         if (d1 >= maxd1)
 40         {
 41             maxd1 = d1;
 42             end2 = i;
 43         }
 44         if (b1 - d1 >= b1)
 45         {
 46             b1 = b1 - d1; 
 47             k--;
 48             k = k - k1;
 49             d1 = 0;
 50             k1 = 0;
 51         }
 52         else{
 53             k1++;            
 54         }    
 55     }
 56 }
 57 void main()
 58 {
 59     int d = 0,d1 = 0;
 60     int j = 0,k = N-1;
 61     srand((unsigned int)time(0));
 62     for (int i = 0;i < 10;i++)
 63     {
 64         a[i] = rand()%50 - 25;
 65         cout << a[i] << " ";
 66         b += a[i];    
 67     }    
 68     b1 = b;
 69     cout << endl;
 70     
 71     //去掉开头结尾的负数
 72     for (int i = 0;i < N;i++)
 73     {
 74         if (a[i] < 0)
 75             j++;
 76         else
 77             break;
 78     }
 79     for (int i = 0;i < N;i++)
 80     {
 81         if (a[N-1-i] < 0)
 82             k--;
 83         else
 84             break;
 85     }
 86 
 87     int x = j,y = k;
 88     zheng(j,k);
 89     ni(x,y);
 90     for (int i = j;i <= y;i++)
 91         b += a[i];
 92     
 93     if (maxd > b)
 94     {
 95         cout << "子数组为：";
 96         for (int i = end2;i <= end1;i++)
 97             cout << a[i] << " ";
 98         cout << endl;
 99         cout << "和为： " << maxd << endl;
100     }
101     else
102     {
103         cout << "子数组为：";
104         for (int i = j;i <= y;i++)
105             cout << a[i] << " ";
106         cout << endl;
107         cout << "和为： " << b << endl;
108     }    
109 }

运行结果截图：