输入一组整数，求子数组和的最大值。
题目:返回一个一维整数数组中最大子数组的和。
要求：
输入一个一维整形数组，数组里有正数也有负数。
一维数组首尾相接，象个一条首尾相接带子一样。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。
10 -9 8 7 -5 3
i ： 4 3 2 1 0
nALL : 3 3 7 15 15 16
nStart: 3 -2 7 15 6 16
nStart = max(arr[i], arr[i]+nStart);
nAll = max(nAll, nStart);
nstart来记录每次和前一个数相加之后的结果，来给原来的nall做比较，而nall则一直表示子数组和的最大值。
当它首尾相接之后，可能会出现比如1,2，-3,4这样的情况，应该是4+1+2是最大的子数组，所以在前面的基础上需要进行一下改进，具体方法如下：
数组本来是1,2，-3,4 现在让每个数做一次数组头，变成一个新数组，例如变成2，-3,4,1还有-3,4,1,2和4,1,2，-3这三个数组，就是把数组进行一次轮换，新来的三个数组依然各进行一次求子数组和的最大值，然后和原来数组的子数组和最大值进行比较，来得出最后的子数组和最大值。
- 源代码：/*求一个数组中子数组的和的最大值。 2016.4.11 底云飞*/
- #include <iostream>
- using namespace std;
- int max(int x, int y)
- {
- return (x > y) ? x : y;
- }
- //求一个数组中子数组和的最大值
- int maxSum2_v(int arr[], int n)
- {
- int i;
- int nAll, nStart; //nAll子数组和的最大值
- nAll = arr[n-1];
- nStart = arr[n-1];
- for(i = n-2; i >= 0; i--)
- {
- nStart = max(arr[i], arr[i]+nStart); //每次和数组的前一个数相加之后，都保留较大的数，
- nAll = max(nAll, nStart); //在上面保留较大数之后，原来的最大和和现在的和比较，取较大值
- }
- return nAll;
- }
- void main()
- {
- //n整数个数，arr【】数组，anotherarr[100]为进行计算的轮换数组，Max字数组和最大值
- int n=100,arr[100],anotherarr[100],Max1=-100,Max=-100;
- cout<<"请输入整数个数：";
- cin>>n;
- cout<<"请输入整数，每个数用空格隔开："<<endl;
- for(int i=0;i<n;i++)
- {
- cin>>arr[i];
- anotherarr[i]=arr[i];
- }
- Max=maxSum2_v(arr,n); //调用maxSum2_v函数
- for(int i=1;i<n;i++) //将数组当中的数进行一次轮换，生成新的另外的数组
- {
- for(int j=0;j<n;j++)
- {
- //开始进行轮换，等号后面需要用arr数组，如果用后来的，则会在多次循环之后，出现数组混乱
- anotherarr[j]=arr[(j+i)%n];
- Max1=maxSum2_v(anotherarr,n); //调用maxSum2_v函数
- }
- if(Max1>Max)
- Max=Max1;
- }
- cout<<"子数组和最大为："<<Max<<endl;
- }
总结：
这次的子数组和练习，将原来的数组首尾相接做成链状之后，比如1,2-3,4这个数组，就会出现4,1,2三个子数组的和最大，而不是从前往后的子数组和最大，所以需要进行数组内部的轮换，让每个值都轮换做一次数组头，然后得出另外的数组，调用求子数组和最大值的方法来求出每个新数组的子数组和最大值，然后进行比较，求得子数组和的最大值。
不能只是简单的将1,2，-3,4想象为1,2，-3,4,1,2，-3这个数组就可以，如果数组都是正数，则会多加求而得错误的最大值。