一、题目及要求:
题目:返回一个整数数组中最大子数组的和
要求(新加):①输入一个二维整形数组,数组里有正数也有负数;②二维数组首尾相接,像一条首尾相接的带子一样。
结对人员:焦燕 胡亚宝
二、设计思路:
这个题目其实就是二维数组和环型数组的结合,要解决这个问题,将之前的两个问题融合一下即可。
首先解决求出二维数组中最大子数组的问题,然后沿用一维数组的方法,将第一列放到最后一列,在求出新的二维数组的最大子数组,依次求出各个二维数组的最大子数组。
三、部分源代码:
1 for (m=0;m<5;m++) 2 { 3 for(cw1=0;cw1<3;cw1++) //将第一列存起来 4 { 5 flag[cw1]=a[cw1][0]; 6 } 7 for(lie=0;lie<4;lie++) //从第二列开始每列的值等于它后面的元素 8 { 9 for(hang=0;hang<3;hang++) 10 { 11 a[hang][lie]=a[hang][lie+1]; 12 } 13 } 14 for(cw2=0;cw2<3;cw2++) //最后一列的值为刚才存的第一列 15 { 16 a[cw2][4]=flag[cw2]; 17 } 18 }
四、心得体会:
感觉如果开始就要解决这个任务,我感觉还是非常难,没有地方下手。但是,经过了前几次的编写程序,感觉这次的程序是前几次的融合。
这次我们两个在讨论的时候,首先考虑到实现第二个功能,即环数组。因为上次我们已经实现了,所以这次感觉挺轻松。但是我们用了很多很多for循环,时间复杂度非常大,这是我们以后需要考虑的问题。
至于实现求二维数组的最大子数组的问题,由于上次我们没有实现,而且现阶段正在专攻电梯系统,所以这次看明白了以后直接实现的是后面的部分。