最大子序列跟最大子矩阵

最大子序列和最大子矩阵

最大子序列:

问题描述:给定整数序列:a1,a2,a3,...an(可能有负数),求a1~an的一个子序列ai~aj,使其和最大

我们很容易想到一个O(n^2)复杂度的方法,即 i : 1--->n,并令 s = 0,然后 j : i---->n, s<---s + a[j],更新maxsum，如若想得到具体的子序列，我们可设i1,j1,更新maxsum时,同时更新下标,不过为了减少运算,我们在更新时做个判断if i1 ≠ i,i1<--i

int sub_sum(int *a,int size,int &i1,int &j1)
{
    int i,j,s,maxsum;
    maxsum = a[0];
    i1 = j1 = 0;
    for(i=0;i<size;i++)
    {
        s = 0;
        for(j=i;j<size;j++)
        {
            s += a[j];
            if(s > maxsum)
            {
                maxsum = s;
                if(i1 != i)
                    i1 = i;
                j1 = j;
            }
        }
    }
    return maxsum;
}

我们注意到,每次在对s求和时,可能遇到部分和小于0,这样的话,显然应该舍弃前面的部分和序列,这实际上有动态规划的思想,复杂度为O(n),具体方法如下:

初设maxsum <--a[0],s=i1 = j1 = temp_i<--0,在扫描数组中,我们记下当前子序列和s,然后试图更新maxsum,j1(<---i),i1(<--temp_i,i1≠temp_i1)再判断s是否小于0,小于则置s = 0,同时更新temp_i为i+1,

#include <stdio.h>
int sub_sum(int *a,int size,int &i1,int &j1)
{
    int i,maxsum,s,temp_i;
    maxsum = a[0];
    i1 = j1 = temp_i = 0;
    s = 0;
    for(i=0;i<size;i++)
    {
        s += a[i];
        if(s > maxsum)
        {
            maxsum = s;
            if(temp_i != i1)
                i1 = temp_i;
            j1 = i;
        }
        if(s < 0)//此处不可用else if,因为有可能s > maxsum且s <0 
        {
            s = 0;
            temp_i = i+1;
        }
    }
    return maxsum;
}
int main()
{
    int a[8] = {4,-3,-4,8,-5,7,-5,7};
    int i,i1,j1;
    printf("%d-->%d:%d\n",i1,j1,sub_sum(a,8,i1,j1));
    return 0;
}

最大子矩阵:

问题描述:给定一个n*m的矩阵A，求A中的一个非空子矩阵，使这个子矩阵中的元素和最大。其中，A的子矩阵指在A中行和列均连续的一块。

思路:m<n时,固定第i列到第j列的范围(否则固定第i到j行)，寻找在这个范围内的最大子矩阵，即把每行第i列上的元素到第j列的元素分别求和，就转变为了一维的情况。由于有C(m,2)种列的组合，而求一维的子序列需要n的时间，所以，总体上时间复杂度为O(n*m*m)。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 501
int a[N][N];
int n,m;
int sub_sum(int *b,int *temp,int *temp1)
{
    int s,max,temp2,i;
    s = max = b[1];
    *temp = *temp1 = temp2 = 1;
    for(i=2;i<=n;i++)
    {
        s += b[i];
        if(s > max)
        {
            max = s;
            if(*temp != temp2)
                *temp = temp2;
            *temp1 = i;
        }
        if(s < 0)
        {
            s = 0;
            temp2 = i+1;
        }
    }
    return max;
}
int main()
{
    int i,j,t,maxsum,s;
    int maxi,maxj,maxi1,maxj1,temp,temp1;
    maxi = maxj = maxi1 = maxj1 = temp = temp1 = 1;
    int *b;
    scanf("%d%d",&n,&m);//行、列
    b = (int *)malloc(sizeof(int)*(n+1));
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
        }
    maxsum = a[1][1];
    for(i=1;i<=m;i++)
    {
        memset(b,0,(n+1)*sizeof(int));
        for(j=i;j<=m;j++)
        {
            //固定i,j列
            for(t=1;t<=n;t++)
                b[t] += a[t][j];//自底向上(m,m,n)
            s = sub_sum(b,&temp,&temp1);
            if(s > maxsum)
            {
                maxsum = s;
                if(temp != maxi)
                    maxi = temp;
                if(temp1 != maxi1)
                    maxi1 = temp1;
                if(i != maxj)
                    maxj = i;
                if(j != maxj1)
                    maxj1 = j;
            }
        }
    }
    printf("(%d,%d)--->(%d,%d):%d\n",maxi,maxj,maxi1,maxj1,maxsum);//最大子矩阵的左上角和右下角坐标点及和
    return 0;
}

参照:http://blog.****.net/luxiaoxun/article/details/7438315
　　

最大子序列跟最大子矩阵

相关推荐