返回一个二维整数数组中最大子数组的和(圆柱形)

题目:

返回一个二维整数数组中最大子数组的和
要求:
输入一个二维整形数组,数组里有正数也有负数。
二维数组首尾相接,象个一条首尾相接带子一样。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
求所有子数组的和的最大值。
组员:
陈晨:负责代码复审和代码测试计划
王颖瑞:负责程序分析,代码编程
思路:
本次的任务是二维数组的环状求最大子数组,结合前两次的开发经验我们把一维数组环状的思路继续在二维数组中使用,首先输入数组时令数组的列扩大一倍,也就是令数组后的数组长度的值与前边的数组长度一一对应相等相当于形环,在利用循环是每一个数组长度的数组进行最大子数组的计算依次技术数组长度个计算比较后求出最大的子数组和。
代码:
#include<iostream>
using namespace std;
void main ()
{
	int k,x,y,i,j,m=0,A[100][100];

	cout<<"输入矩阵的行()和列";
	cin>>x>>y;
	if(x>100||y>100)
	{
		cout<<"请重新输入:";
		cin>>x>>y;
	}
	for(i=0;i<x;i++)
	{
		for(j=0;j<y;j++)
		{
			cin>>A[i][j];
			A[i][j+y]=A[i][j];
		}
	}
	int sum[100]={0},max=0,result=A[0][0];
	for(k=0;k<y;k++)
	{
		for(i=0;i<x;i++)//确定子数组的最大上界(为第i行)
		{
			while(m+i<x)//确定子数组有m+i行
			{
				//把子数组当成一位数组一样,求最大子数组的和
				for(j=k;j<y+k;j++)
				{
					sum[j]=sum[j]+A[m+i][j];

				}
				max=0;
				for(j=k;j<y+k;j++)
				{
					if(max+sum[j]>sum[j])
					{
						max=max+sum[j];
					}
					else
					{
						max=sum[j];
					}
					if(max>result)
					{
						result=max;
					}
				}
				m++;//是子数组的行数+1
			}
			//初始化m和sum[]的值,使子数组最大上界下降1,之后重新循环。
			m=0;
			for(j=k;j<k+y;j++)
			{
				sum[j]=0;
			}

		}
	}

	cout<<result;
}

截图:

总结:

这次的结对开发任然是数组的问题在本次的任务中我们利用了一维数组的思路,这让我知道了一些比较复杂的问题可以通过简单化来设计思路,结对开发也有过了几次的开发经验现在在结对开发中也有了一定的默契,体会到了结对开发的好处。

原文地址:https://www.cnblogs.com/lingxi/p/4440920.html