今天所做的小程序是接着上次的一位数组的最大子数组，上次运用了两种方法对一位数组进行求最大子数组，分别是：穷举法和动态规划的方法。今天是对二维数组进行求解，可以在考虑一种利用上次的动态规划，试着将二维数组转化为一位数组进行求解，对二位数组暂时想到的是穷举法：
我们想,如果确定了选择第i列和第j列之间的元素，那么在这个范围内，其实就是一个最大子序列问题：
程序代码：
package com.su.test;
public class Hellosu {
public static void main(String[] args)
{
//测试用例
int b[][]={{3,4,-7},{7,2,0},{-11,3,0}};
int max=maxSubMatrix(b,b.length,b[0].length);
System.out.println(max);
}
public static int maxSubArray(int ar[],int n) //一维数组最大子数组
{
int max=ar[0];
int k[]=new int[3];
int b=ar[0];
int i;
for(i=1;i<n;i++)
{
if(b>0)
{
b+=ar[i];
}
else
{
b=ar[i];
}
if(b>max)
{
max=b;
}
}
return max;
}
public static int maxSubMatrix(int p[][],int m,int n) //二维数组最大子矩阵
{
int i,j,k,max=p[0][0],tempt;
//记录每行的和
int last_i=0,last_j=0;
int sum[]=new int[m];
for(i=0;i<n;i++)
{
for(k=0;k<m;k++)
sum[k]=0;
for(j=i;j<n;j++)
{
for(k=0;k<m;k++)
{
sum[k]+=p[k][j];
}
tempt=maxSubArray(sum,m);
if(tempt>max)
{
last_i=i;
last_j=j;
max=tempt;
}
}
}
System.out.println("从第"+(last_i+1)+"列开始,到第"+(last_j+1)+"结束");
return max;
}
}
运行结果截图：
