首页 > 其他 > 详细

求二维数组的最大子数组

时间:2014-03-19 21:36:19      阅读:455      评论:0      收藏:0      [点我收藏+]

郑云飞--韩亚华 

还接的前几天的求一位数组的子数组,我们看懂了同学各种各样的思路。比如李帅-张硕组的方法就很简答易懂

如下:

bubuko.com,布布扣
int max(int list[],int length)
 2 {
 3     int sum ;
 4     int i,j;
 5     int max = list[0];
 6     for(i = 0; i<length; i++)
 7     {
 8         sum=0;
 9         for(j = i;j<length; j++)
10         {
11             sum=sum+list[j];
12             if(sum>max)
13             {
14                 max = sum;
15             }
16         }
17     }
18     return max;
bubuko.com,布布扣

还有网上找的算法:

bubuko.com,布布扣
 for(int i = 0;i < 12;i++)  
   {  
      if(sum >= 0)//如果加上某个元素,sum>=0的话,就加  
      {  
         sum += a[i];  
      }  
      else        //如果加上某个元素,sum<0了,就不加,从当前位置开始  
      {  
         sum = a[i];  
      }  
      if(sum > max)max = sum;  
   }  
   return max;
bubuko.com,布布扣

于是我们想能否用以上两种解决这个问题,思路是将二维数组的列或行的子数组的和看成一个新的一维数组的元素。

这样我们就能用到上面的方法实现。这样我们就能简化一部分计算。不过后来我发现有同学和我的像很想,并且他

非常巧妙的实现了(见链接),所以我不再赘述。

http://www.cnblogs.com/sulindong/p/3607523.html

 于是我们开始思考别的思路,就如同一维数组的最大子数组是以非负数开头和非负数结尾的,二位子数组的外围行

和列的和肯定也是非负数。如果我们能遍历具有这样特征的字数组,在很多时候就能化简一部分枚举。但这样会使算

法的实现很麻烦,所以我们暂时没采用。所以我们还没有很好的算法。。。。

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

求二维数组的最大子数组

原文:http://www.cnblogs.com/hanyahua/p/3612213.html

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