返回整数数组最大子数组和2

题目与要求：

　　题目:返回一个整数数组中最大子数组的和。
　　要求：
　　　　输入一个整形数组，数组里有正数也有负数。
　　　　数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
　　　　如果数组A[0]……A[j-1]首尾相邻，允许A[i-1]， …… A[n-1]， A[0]……A[j-1]之和最大。
　　　　同时返回最大子数组的位置。
　　　　求所有子数组的和的最大值。

　
设计思路：

对于这次的要求本来想在以前的基础上继续添加功能，但是以前的算法没有办法加入返回位置，就用了新的方法。首先实现的是数组首尾相连，先存入数组，再将原数组反向存储形成环形数组。接着求最大子数组的和，遍历数组里面的每一个数将第一个数变成为最后一个数，形成一个新的数组，计算数组中每个最大子数组的和存入另一个数组max【】中，并记录最大子数组位置，最后找max【】数组中最大值为所求。

程序代码：

//返回整数数组最大子数组和2
//孔宇航 赵子茵 2016/3/25

#include <iostream>
using namespace std;
#define N 1000
int main(int argc, char* argv[])
{
    int arry[N];
    int length=1;
    int max[N],max1; //max[N]存每一次求和的结果，在其中找最大值，为所求
    int maxweizhi[N];
    int num=0;
    int value( int arry[],int length);
    cout<<"请输入数组："<<endl;
    cin >> arry[0];
    while (getchar() != '\n')      //输入数组
    {
        cin >> arry[length];
        length++;
    }
   
     for(int j=length;j<2*length-1;j++)   //形成环形数组，首位相连
    {
        arry[j]=arry[num];
        num++;
    }
 
    cout<<"由这几个数形成的环形数组";
    value(arry,2*length-1);
    return 0;
}
int value( int arry[],int length)
{
    int max[N],max1;
    int maxweizhi[N];
    for(int j=0;j<(length+1)/2;j++)
    {
        int sum=0;
        max1=-9999999;                   //设置最低范围
        int z=0;
        for(int i=j;i<(length+1)/2+j;i++)   //环形数组找最大子数组和
        {
            sum=sum+arry[i];
            if(sum>=max1)
            {
                max1=sum;
                z++;
            }
        }
        max[j]=max1;
        maxweizhi[j]=z;
     
    }
    int fmax=max[0];
    int q=0;
    for(int i=0;i<(length+1/2);i++)  //在所有和的数组中找最大值
    {   
        if(max[i]>fmax)
        {
            fmax=max[i];
            q=i;
        }
    }
 
    int weizhi=maxweizhi[q];
 
    cout<<"最大子数组为："<<endl;
    for(int num=q;num<q+weizhi;num++)  //输出最大子数组的位置
    {
        cout<<arry[num];
    }
 
    cout<<"其和为:  "<<fmax<<endl;
    return 0;
}

实验截图：

实验总结：

对于此次实验，在上一次的基础上添加了新的功能，由于上次方法不合理我们决定开辟新道路，用了新的方法，过程还算顺利，对于数组连城环的问题出现过误区，我们尝试过把数组平铺成一个新的一位数组，后来发现结果是不对的，所求子数组数量太多不合题意。经过改正实验顺利完成，跟小伙伴合作很愉快，其实还是有小吵小闹，但总的来说还算“互补”，希望在以后的合作中更加默契，程序更加完善标准。

附上小伙伴链接：http://www.cnblogs.com/kongyuhang/p/5320585.html

返回整数数组最大子数组和2

返回整数数组最大子数组和2

推荐阅读