首页 > 编程语言 > 详细

循环数组求最大子数组

时间:2015-03-29 01:45:08      阅读:263      评论:0      收藏:0      [点我收藏+]

一、题目要求

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

二、设计思想

把数组每一位向后移动一位,最后一位放在第一位。循环多次,每次求其最大子数组,存放到新数组内,比较新数组中最大数,并输出。

三、源代码

#include <iostream.h>
int Largest(int list[],int length)
{
 
    int n,max=list[0];/
 
    for(n=0;n<=(length-1);n++)
    {
        if(list[n]>max)
        {
            max=list[n];
        }
    }
    return max;
}
int MaxSum2(int *A, int n)
{
    int nStart = A[n-1];
    int nAll = A[n-1];
    for(int i = n-2;i>=0;--i)
    {
        if(nStart<0)
            nStart = 0;
        nStart += A[i];
        if(nStart>=nAll)
        {
            nAll = nStart;
        }
    }  
    return nAll;
}
int main(void)
{
    int sum[5]={1,-2,-3,-4,5};
    int sum2[15]={0};
    int gg[5]={0};
    int kk[5]={0};
    int t;
    for(int k=0;k<5;k++)
    {
        t=sum[4];
        for(int j=3;j>=0;j--)
        {sum[j+1]=sum[j];}
        sum[0]=t;
        gg[k]=MaxSum2(sum,5);      
    }
    cout<<Largest(gg,5)<<endl;
}
  

四、结果截图

技术分享

五、心得体会

结对开发,是你潜力的开始,只要你投入进去你就会有不一样的收获,我们结对开发目前已经进行了几次了,每一次我们两个人都会进行激烈的讨论,然后对每一个人的思路进行验证,最后我们每次都能找出一种解决问题的方法。这一对于循环数组的问题我们又遇到了一些问题,问题一就是我们要怎样才能让它循,我们尝试了几种方法,最后找到了比较合适的。还有就是写代码时候遇到了一些问题,不过通过几次调试之后也得到了解决。感谢这么多次队友(程鹏远)的并肩作战。

循环数组求最大子数组

原文:http://www.cnblogs.com/hushunli/p/4375109.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!