最大子数组问题：在一位数组中A[1...n]中，取连续的m个元素A[i...i+m]，其中1<=i<=m<=n，使得A[i...i+m]的和最大
最大子矩阵问题：在一个矩阵A[m*n]中，任意截取一个矩形区域，使得截取的元素和最大
这两个问题是类似的，最大子矩阵问题是在最大子数组的扩展，下面最大子数组的思路和代码：
/************************************************************************/
/* 题目说明：在一维数组中求最大子数组和
All[i,j]表示从A[i
j]中和最大的1段
Start[i,j]表示A[ij]中包含i的和最大的1段
则All[i-1,j] = max(Start[i-1,j], All[i,j])，其中
Start[i-1,j] = max(Start[i,j]+A[i-1],A[i-1]),
而初始条件为Start[n-1] = A[n-1],All[n-1] = A[n-1]
/* 测试数据
6 [1 -2 3 5 -3 2] 结果8
6 [0 -2 3 5 -1 2] 结果9
5 [-9 -2 -3 -5 -3] 结果-2
/************************************************************************/
#include<iostream>
using namespace std;
int main()
{
int n,i,start,al,index,alindex;
while(1)
{
cout<<"输入元素个数：";
cin>>n;
int *a = new int[n];
cout<<"输入元素值：";
for(i=0;i<n;i++)
{
cin>>a[i];
}
al = a[n-1];
start = a[n-1];
alindex = n-1;
for(i=n-2;i>=0;i--)
{
if(start>0)
{
start = start+a[i];
}
else
{
start = a[i];
}
if(start>al)
{
al = start;
alindex = i;
}
}
cout<<alindex<<" "<<al<<endl;
delete a;
}
return 0;
} 最大子矩阵问题的思路是将位于i行和j行之间的同一列元素打包为一个元素，相当于求一个长度为n的数组的最大子数组。枚举从1到m行的所有情况(1,1..2,1...3,1...m,2,2...3等等)，求出最大值。下面是poj1050的程序：
/************************************************************************/
/* 求最大子矩形问题
将每一列打包，枚举
bc[i][j]表示第i列0j行元素之和
/************************************************************************/
#include<iostream>
using namespace std;
int main()
{
int n,a[100][100],i,j,k,bc[100][100],al,starti;
//读入数据
cin>>n;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cin>>a[i][j];
}
}
memset(bc,0,sizeof(int)*10000);
//bc[i][j] = bc[0][j]-bc[0][i];
for(i=0; i<n; i++)
{
for(j=0;j<n;j++)
{
if(j==0)
{
bc[i][0] = a[0][i];
}
else
{
bc[i][j] = bc[i][j-1] + a[j][i];
}
}
}
int m = -1270000;
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)
{
starti = bc[n-1][j] - bc[n-1][i];
al = bc[n-1][j] - bc[n-1][i];
for(k=n-2;k>=0;k--)
{
if(starti<0)
{
starti = 0;
}
starti += bc[k][j] - bc[k][i];
if(starti>al)
{
al = starti;
}
if(al>m)
{
m = al;
}
}
}
}
cout<<m<<endl;
return 0;
}
posted on 2011-08-17 10:22
成成 阅读(1393)
评论(0) 编辑 收藏 引用