xmu1031 to the max

问题描述：这个题目的意思很简单，有一个举证A[n][n],要从这个矩阵中找到一个子矩阵（至少为1×1），使得这个子矩阵的各项相加值最大。

从网上找了一下算法，用动态规划来做它是很确定的，参考了一位老兄的博客，写的很详细，也很容易理解，大家想看看可以点击上一行的“动态规划”，已经设置好链接。

这个题目首先要从一位的说起：

有 A1 A2 A3……An项，我们要求其一个字列，使得这个字列各项之和最大？？

方法：1.遍历，计算出所有的可能性，这无疑是效率最低的一种方法，O（n^3)；
    for(int i=0;i<n;i++)
    for(int j=i;j<n;j++)
    {
    int temp ;
    for(int k=i;k<=j;k++)
    temp =+ A[k];
    sum=sum>temp?sum:temp;
    }
    2.利用已有的计算结果可以减少一重for 循环，O(n^2)
    for(int i=0;i<n;i++) {
    int temp ;
    for(int j=i;j<n;j++)
    {
    temp=+A[j];
    sum=sum>temp?sum:temp;
    }
    }
    3.利用动态规划的处理，复杂度为O(n),空间复杂度也为O(n);
    int sum = -1000 , temp = 0;
    for(int i=0;i<n;i++)
    {
    if( temp >0) temp =+ A[i];
    else temp = A[i];
    sum=sum>temp?sum:temp;
    }

注意第三种方法，动态规划。因为在后面二维矩阵中将他推广一下。

    A11 A12 A13. . . . . . . . . A1n

    A21 A22 A23. . . . . . . . . .A2n
    . . . . . . . . . . . . . . .. . . . . .. . . .
    . . . . . . . . . . . . . . . . . . . . . . . .
    . . . . . . . . . . . . . . . . . . . . . . . .
    An1 An2 An3 . . . . . . . . . .Ann

上面是一个n*n的矩阵，现在要求它的最大子矩阵。

我们考虑这样一个数列[Ai1+..+Aj1 , Ai2+..+Aj2, Ai3..+Aj3 , Ai4..+ Aj4, .... , Ain...+ Ajn ],很熟悉。

上面这个数列的最大子序列便可以使用动态规划来求出。

到底有多少个这样的呢？？ 这时我们关注一列，从第一列到第n列，一列n个数字[1,2,.......n] , 从中截取[i,...j];

    我们用两个for循环便可以解决截取的问题。最终程序代码贴在下面

    #include<iostream>
    #include<cstdlib>
    #define max 105
    int array[max][max];
    using namespace std ;
    int SubMax(int n,int* p)
    {
    int sum = -1000 ;
    int u = 0 ;
    for(int i=0;i<n;i++)
    {
    if(u<0) u = p[i];
    else u = p[i]+ u ;
    sum=u>sum?u:sum;
    }
    return sum ;
    }
    int main()
    {
    int number;
    int sum = -1000;
    cin>>number;
    if(number==1)
    {
    cin>>number;
    cout<<number<<endl;
    }
    else {
    for(int i=0;i<number;i++)
    for(int j=0;j<number;j++)
    cin>>array[i][j];
    int*point = new int[number];
    for(int i=0;i<number;i++)
    {
    for(int s=0;s<number;s++) //每次移动i后，对数组进行初始化

    point[s]=0;
    for(int j=i;j<number;j++)
    {
    for(int k=0;k<number;k++)
    point[k]=point[k]+array[j][k];
    int temp=SubMax(number,point);
    sum = sum>temp?sum:temp;
    }
    }
    cout<<sum <<endl;
    }
    system(“pause”);
    return 0 ;
    }