返回一个首尾相连的整数数组中最大子数组的和

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

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

二、要求：

（1）n输入一个整形数组，数组里有正数也有负数。

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

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

（4）n同时返回最大子数组的位置。

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

三、实验思路：

思路一：将一个数组的元素输入，构造一个新数组，新数组是由两遍输入的数组构成，然后按照一维数组的求法求出，前提要加上限制条件，求和时数组的长度必须小于输入数组的个数。

思路二：输入一个数组后，求其最大子数组，然后再将第一个数排到末尾，再开始求最大字数组，直到最后一个数组元素为第一位置为止。

四、实验代码：

思路二代码：

#include<iostream>
using namespace std;

void main()
{
    int length;   //数组的个数
    int n;       //数组变化后的长度
    cout<<"请输入数组元素个数："<<endl;
    cin>>length;
    n=2*length;    

    int *a=new int[n];  //定义数组
    cout<<"请输入数组的元素："<<endl;
    for(int i=0;i<length;i++)// for循环依次输入数组的元素
    {
        cin>>a[i];
    }
    int max=a[0];   // 首先定义max并且赋予第一个数组中的元素值
    int s=0;   //定义s值，s值为数组元素之和并且与max值比较
    for(int i=0;i<length;i++)
    {
        s=0;    
        for(int j=i;j<length+i;j++)
        {
            s=s+a[j];
            if(s>max)
            {
                max=s;
            }    
        }
        a[length+i]=a[i];
    }
    cout<<endl;
    cout<<"最大子数组的和为："<<endl;
    cout<<max<<endl;
}