最大子數(shù)組問題：在一位數(shù)組中A[1...n]中，取連續(xù)的m個元素A[i...i+m]，其中1<=i<=m<=n，使得A[i...i+m]的和最大
最大子矩陣問題：在一個矩陣A[m*n]中，任意截取一個矩形區(qū)域，使得截取的元素和最大
這兩個問題是類似的，最大子矩陣問題是在最大子數(shù)組的擴展，下面最大子數(shù)組的思路和代碼：
/************************************************************************/
/* 題目說明：在一維數(shù)組中求最大子數(shù)組和
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]
/* 測試數(shù)據(jù)
6 [1 -2 3 5 -3 2] 結(jié)果8
6 [0 -2 3 5 -1 2] 結(jié)果9
5 [-9 -2 -3 -5 -3] 結(jié)果-2
/************************************************************************/
#include<iostream>
using namespace std;
int main()
{
int n,i,start,al,index,alindex;
while(1)
{
cout<<"輸入元素個數(shù)：";
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的數(shù)組的最大子數(shù)組。枚舉從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;
//讀入數(shù)據(jù)
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
成成 閱讀(1434)
評論(0) 編輯 收藏 引用