•  
  • 数据结构和算法
  • 【POJ1050】To the Max (动态规划、最大字串和、最大子矩阵和)||NYOJ44 ||NYOJ104

【POJ1050】To the Max (动态规划、最大字串和、最大子矩阵和)||NYOJ44 ||NYOJ104

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 04 月 25 日

其实就是最大子段和问题在二维空间上的推广。先说一下一维的情况吧:设有数组a0,a1…an,找除其中连续的子段,使它们的和达到最大。假如对于子段:9 2 -16 2  temp[i]表示以ai结尾的子段中的最大子段和。在已知temp[i]的情况下,求temp [i+1]的方法是:

如果temp[i]>0 temp [i+1]= temp[i]+ai(继续在前一个子段上加上ai),否则temp[i+1]=ai(不加上前面的子段),也就是说 状态转移方程:

temp[i] = (temp[i-1]>0?temp[i-1]:0)+buf[i];

对于刚才的例子 temp: 9 11 -5 2,然后取temp[]中最大的就是一维序列的最大子段。求一维最大子段和的函数:

int getMax(int buf[100],int n)

{

int temp[101],max=n*(-127);

memset(temp,0,4*(n+1));

 

for(int i=1;i<=n;i++)

{

temp[i] = (temp[i-1]>0?temp[i-1]:0)+buf[i];

if(max<temp[i])

max=temp[i];

}

return max;

}

下面扩展到二维的情况:考察下面题目中的例子:

0  -2  -7  0

9   2  -6  2

-4  1  -4   7

-1  8  0   -2

我们分别用i j表示起始行和终止行,遍历所有的可能:

for(i=1;i<=n;i++)

for(j=i;j<=n;j++) {}

我们考察其中一种情况 i=2 j=4,这样就相当与选中了2 3 4三行,求那几列的组合能获得最大值,由于总是 2 3 4行,所以我们可以将这3行”捆绑”起来,变为求 4(9-4-1),11(8+2+1),-10(-6-4+0),7(7+2-2)的最大子段和,ok,问题成功转化为一维的情况!

最大子串和:

 

#include<cstdio>  
#include<iostream>  
#include<climits>  
using namespace std;  
const int MAX=1000010;  
int a[MAX]={0};  
int main()  
{  
    int n,m,maxsum;  
    scanf("%d",&n);  
    while(n--)  
    {  
        maxsum=-INT_MAX;  
        scanf("%d",&m);  
        for(int i=1;i<=m;++i)  
        {  
            scanf("%d",&a[i]);  
            if(a[i-1]>0) a[i]+=a[i-1];  
            if(a[i]>maxsum) maxsum=a[i];  
        }  
        printf("%d\n",maxsum);  
    }  
}  

最大子矩阵和:

#include<iostream>  
#include<cstring>  
using namespace std;  
#define N 110  
int a[N][N];  
int b[N];  
int main(){  
    int n,r;  
    cin>>r;  
    for(int i=1;i<=r;++i)          
        for(int j=1;j<=r;++j)  
        {  
            cin>>a[i][j];  
            a[i][j]+=a[i-1][j];  
        }  
        int max=a[1][1];  
        for(int i=0;i<=r-1;++i)  
            for(int j=i+1;j<=r;++j)  
            {  
                memset(b,0,sizeof(b));  
                for(int k=1;k<=r;++k)  
                {  
                    if(b[k-1]>=0)  
                        b[k]=b[k-1]+a[j][k]-a[i][k];  
                    else  
                        b[k]=a[j][k]-a[i][k];  
                    if(max<b[k])  
                        max=b[k];  
                }  
            }  
    cout<<max<<endl;  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期日, 2017 年 12 月 17 日