首页 > 其他 > 详细

求二维数组中最大子数组的和

时间:2014-03-19 18:25:54      阅读:473      评论:0      收藏:0      [点我收藏+]


任国庆  张博

之前我们讨论了在一维数组中求最大子数组的和,在此基础上我们开始讨论二维数组的最大子数组。

求二维数组的最大子数组思想是建立在以为数组。首先将数组的第一列看成一个一维数组,找到该列的最大子数组的值,然后将第二列与第一列看成是一个新一列,这样就又出现了一个新的一维数组,重复以上的步骤,就可以全部搜索二维数组,找到其中最大子数组的值。

bubuko.com,布布扣
#include "stdafx.h"
int main()
{

    int m,n,i,j,k,z;
    static int  q=0,b;
    printf("请输入数组的行数和列数\n");
    scanf("%d%d",&q,&b);
    int sum1,sum[100];
    int a[100][100];
    int max=0;
    printf("请输入数据\n");
    for(i=0;i<q;i++)
    {
        for(j=0;j<q;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    for(m=0;m<q;m++)
    {
        for(k=0;k<q;k++)
        {
            sum[k]=0;
        }                            //初始化
        for(j=m;j<q;j++)
        {
            for(i=0;i<q;i++)
            {
                sum[i]+=a[i][j];

            }                       //求行的值变成一维数
            for(n=0;n<q;n++)
            {
                sum1=0;
                for(z=n;z<q;z++)
                {
                    sum1+=sum[z];
                    if(sum1>max)
                    {
                        max=sum1;
                    }
                }
            }
        }
    }
    printf("最大值为%d\n",max);
    return 0;
}
bubuko.com,布布扣

一下是我们组讨论的图
bubuko.com,布布扣

实验结果

bubuko.com,布布扣

实验猜想

基于以上的讨论我们组找到了二维数组中最大子数组的值,但是这方法比较笨,时间复杂度是O(n*3).所以我们猜想应该找到一个算法,以数组中最大值为一点,进行扩散的寻找最大子数组的值,这样程序执行起来时间复杂度会降低,因此我们组将继续讨论,以降低时间复杂度.

求二维数组中最大子数组的和,布布扣,bubuko.com

求二维数组中最大子数组的和

原文:http://www.cnblogs.com/zhangbo2011/p/3611741.html

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