最大子阵

/*问题描述
　　给定一个n*m的矩阵A，求A中的一个非空子矩阵，使这个子矩阵中的元素和最大。

　　其中，A的子矩阵指在A中行和列均连续的一块。
输入格式
　　输入的第一行包含两个整数n, m，分别表示矩阵A的行数和列数。
　　接下来n行，每行m个整数，表示矩阵A。
输出格式
　　输出一行，包含一个整数，表示A中最大的子矩阵中的元素和。
样例输入
3 3
-1 -4 3
3 4 -1
-5 -2 8
样例输出
10
样例说明
　　取最后一列，和为10。
数据规模和约定
　　对于50%的数据，1<=n, m<=50；
　　对于100%的数据，1<=n, m<=500，A中每个元素的绝对值不超过5000。*/
package test;
import java.util.*;
public class 最大子阵 {
    //static int[] s,d;
    public static void main(String arg[]){
        int[] s=new int[510],dp=new int[510];  
        int[][] a=new int[510][510];
        int n,m,i,j,k,temp;  
            int max=-100000000;  
            Scanner input=new Scanner(System.in);
            n=input.nextInt();
            m=input.nextInt();
            for(i=1;i<=n;i++)  
            {  
                for(j=1;j<=m;j++)  
                {  
                    a[i][j]=input.nextInt();  
                }  
            }  
              
            for(i=1;i<=n;i++)  //起点行
            {  
                for(int l=0;l<s.length;l++){ s[l]=0;}  
                for(j=i;j<=n;j++)   //终点行
                {  
                    for(k=1;k<=m;k++)   //列上的遍历
                    {  
                        s[k]=s[k]+a[j][k];  
                                  
                        if(dp[k-1] > 0)     //状态转移——“拖累思想”。若dp[k-1]>0则不会拖累当前数。
                        {  
                             dp[k] = dp[k-1]+s[k];    
                        }else{  
                             dp[k] = s[k];  
                        }  
                        if(dp[k]>max)  
                        {  
                            max = dp[k];  
                        }  
                    }  
                }  
            }  
              
           System.out.print(max);
           }
    }