posts - 3,  comments - 4,  trackbacks - 0
最大子数组问题:在一位数组中A[1...n]中,取连续的m个元素A[i...i+m],其中1<=i<=m<=n,使得A[i...i+m]的和最大
最大子矩阵问题:在一个矩阵A[m*n]中,任意截取一个矩形区域,使得截取的元素和最大

这两个问题是类似的,最大子矩阵问题是在最大子数组的扩展,下面最大子数组的思路和代码:
/************************************************************************/
/* 题目说明:在一维数组中求最大子数组和
 All[i,j]表示从A[ij]中和最大的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 *= 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 成成 阅读(1371) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理