求二维数组的最大子数组——

继上节课老师让求了一维数组最大的子数组后，这节课堂上，老师加深了难度，给了一个二维数组，求最大子数组，开始觉得很容易，但是自己思考起来感觉这个算法很困难，既需要考虑数组直接的连续，又要求出最大的，老师提供的思路是找最大的数所在的位置是结果的可能性会大一点，或者是负数少的可能性会大一些，但这也只是一个概率问题，求解起来还是比较麻烦，也想过用二叉树，但是不能确保数组的连续性，所以只能想用一个个遍历的方法，经过自己的思考后又上网看了别人的程序，下面大家一起探讨一下吧！

#include <iostream>

#include <string>

int main(void)

{

    int a[][];

    int st[][];

    int p,k,n,i,j,sum,max;

    scanf("%d",&n);

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

        for (j=;j<=n;j++)

            scanf("%d",&a[i][j]);

    memset(st,,sizeof(st));

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

        for (j=;j<=n;j++)

            st[i][j]=st[i][j-]+a[j][i];

    max=;

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

    {

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

        {

            p=st[][j]-st[][i-];

            sum=p;

            for (k=;k<=n;k++)

            {

                if (sum>)

                    sum+=st[k][j]-st[k][i-];

                else

                    sum=st[k][j]-st[k][i-];

                if (sum>p)

                    p=sum;

            }

            if (p>max) maxn=p;

        }

    }

    printf("%d\n",max);

    return ;

}

常用于数组的初始化, st是一个数组，将它的所有元素初始化为0 memset(st/*数组名*/,0/*要赋予的值*/ ,sizeof(st)/*数组元素个数*/);

巴特西

求二维数组的最大子数组———曹玉松&&蔡迎盈

最新文章

热门文章