二维数组最大子数组
一.题目:
返回一个二维整数数组中最大子数组的和。 要求： 输入一个二维整形数组，数组里有正数也有负数。 二维数组中连续的一个子矩阵组成一个子数组，每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)。
二：结对编程要求：
两人结对完成编程任务。 一人主要负责程序分析，代码编程。 一人负责代码复审和代码测试计划。 发表一篇博客文章讲述两人合作中的过程、体会以及如何解决冲突(附结对开发的工作照)。
三.代码：
#include <iostream>
#include <cstring>
//#include<vector>
//#include<cstdio>
#define NDEBUG
#include <assert.h>
//#define INF -9999
//#define N 100
//?与设置全局变量有什么区别
const int N = 500;
const int INF = -9999;
using namespace std;
int maxSubArray(int a[], int n)
{
assert(a!=NULL && n>0);
int cur = 0;
int max = INF;
for (int i=0; i<n; i++)
{
cur +=a[i];
if (cur < 0)
{
cur = 0;
}
if (cur > max)
{
max = cur;
}
}
return max;
}
int findMaxSubMatrix(int a[][N], int n) //?思考为什么这里是a[][N]
{
int tmpSum[N];
int max = INF;
//枚举所有行的可能组合
for (int i=0; i<n; i++)
{
//将tmpSum清零
memset(tmpSum, 0, sizeof(tmpSum));
for (int j=i; j<n; j++)
{
//加上当前行的元素
for(int k=0; k<n; k++)
{
tmpSum[k] += a[j][k];
}
int tmpMax = maxSubArray(tmpSum, n);
if(tmpMax >max)
{
max=tmpMax;
}
}
}
return max;
}
int main()
{
int a[N][N];
int n; //数组的大小
cout<<"请输入数组n*n中n的大小: "<<endl;
while (cin>>n && n)
{
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
int k=rand();
a[i][j]= k%2==0? rand()%100+1 : -(rand()%100+1);
}
}
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
cout<<"最大子数组的和为: "<<findMaxSubMatrix(a, n)<<endl;
}
return 0;
}
四.思想：
程序中涉及到的两个函数：
1. assert(a!=NULL && n>0);
assert宏的原型定义在<assert.h>中，其作用是如果它的条件返回错误，则终止程序执行，原型定义：
#include <assert.h>
void assert( int expression );
assert的作用是现计算表达式 expression ，如果其值为假（即为0），那么它先向stderr打印一条出错信息，然后通过调用 abort 来终止程序运行。
已放弃使用assert()的缺点是，频繁的调用会极大的影响程序的性能，增加额外的开销。在调试结束后，可以通过在包含#include <assert.h>的语句之前插入 #define NDEBUG 来禁用assert调用，示例代码如下：
#include <stdio.h>
#define NDEBUG
#include <assert.h>
2. memset(tmpSum, 0, sizeof(tmpSum));
将tmpSum清零
需要的头文件
C中为<memory.h> 或 <string.h>
C++中为<cstring>
void * memset ( void * ptr, int value, size_t num );
为地址ptr开始的num个字节赋值value，注意：是逐个字节赋值，ptr开始的num个字节中的每个字节都赋值为value。
（1） 若ptr指向char型地址，value可为任意字符值；
（2） 若ptr指向非char型，如int型地址，要想赋值正确，value的值只能是-1或0，因为-1和0转化成二进制后每一位都是一样的，设int型占4个字节，则-1=0XFFFFFFFF, 0=0X00000000。
思路：
程序的时间复杂度为O(n^3)。findMaxSubMatrix（）找出最大的子数组之和，i控制行，它是一行一行的往下找最大子数组，比如当i等于2时，在同一列的数相当于一维数组中的一个数，每到i加1，调用maxSubArray(int a[], int n)找出这个一维数组的最大子数组之和，再将它与maxnum作比较看哪个更大。
缺陷：时间复杂度还是很大，而且这个最大子数组也没想到怎么输出
4.测试：
当n=4时
当n=50时
五.工作照
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。