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

一、题目: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;
}

 

五、实验截图:
技术分享
六、实验总结:
           思路一的关键是找到算法的限制条件,怎样能满足题目要求,思路二还不能返回最大子数组的位置,通过此次问题的分析与结对开发过程当中所出现的问题,我们还尚有很多不足之处,还需要再接再厉。
七、队友:郎国杰、刘伯建

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。