二维循环数组最大子数组的和
结对成员:于海洋 袁佩佩
一.题目及要求
题目:返回一个二维整数数组中最大子数组的和。
要求: 输入一个二维整形数组,数组里有正数也有负数。
二维数组首尾相接,象个一条首尾相接带子一样。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
二.设计思路
用之前的二维数组求最大子数组的和的代码,将控制条件改一下。每次循环时,第一行循环len1个数,len1是数组的列数等到循环到末尾时,再接上第一列…
三.源代码
// 二维数组循环.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "fstream.h" #include "iostream.h" #define MAXSIZE 50 //*****读取数组信息***** void ReadArr(int arr[][MAXSIZE],int &len1,int &len2) { ifstream infile("Arr.txt"); if(!infile) cout<<"读取失败!"<<endl; else { infile>>len1>>len2; for(int i=0;i<len1;i++) { for(int j=0;j<len2;j++) { infile>>arr[i][j]; //从文件中读取数据 arr[i][j+len2]=arr[i][j]; } } } } //*****显示矩阵***** void ShowArr(int arr[][MAXSIZE],int len1,int len2,int size1,int size2) { for(int i=len1;i<=size1;i++) //将文件中的数组输出 { for(int j=len2;j<=size2;j++) { cout<<arr[i][j]<<"\t"; } cout<<endl; } } //*****求和公式***** int GetSum(int arr[][MAXSIZE],int len1,int len2,int size1,int size2) { int sum=0; for(int i=len1;i<=size1;i++) //求任意数组中两个数之间的数的和 { for(int j=len2;j<=size2;j++) { sum+=arr[i][j]; } } return sum; } int main(int argc, char* argv[]) { int len1,len2,max,sum; //len1是行数,len2是列数 int line1,line2,row1,row2; //和最大的矩阵的两个坐标 int arr[MAXSIZE][MAXSIZE]; ReadArr(arr,len1,len2); cout<<"矩阵:"<<endl; ShowArr(arr,0,0,len1-1,len2-1); cout<<endl; line1=0; line2=0; row1=0; row2=0; sum=0; max=arr[0][0]; for(int i=0;i<len1;i++) //第一个数的行数 { for(int j=0;j<len2;j++) //第一个数的列数 { for(int m=i;m<len1;m++) //第二个数的行数 { for(int n=j;(n<2*len2)&&(n<j+3);n++) { //第二个数的列数 sum=GetSum(arr,i,j,m,n); //求出这两个数构成的矩阵的和 if(sum>max) { max=sum; line1=i; //保存第一个数的行 line2=m; //保存第二个数的行 row1=j; //保存第一个数的列 row2=n; //保存第二个数的列 } } } } } cout<<"和最大的子矩阵:"<<endl; ShowArr(arr,line1,row1,line2,row2); cout<<"最大的和:"<<max<<endl; return 0; }
四.结果及截图
五.体会
六.结对合照
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。