最大连续子段和有各种方法，很多的都含着暴力的解法，一维O(n)的解法的也已经很熟悉了～现在复习一下，便于进行拓展
最大连续子段和
a[]数组存储原序列，dp[i]表示处理完第i个数后（包括第i个数在内）的目前最大连续字串
dp[i] = dp[i-1]+a[i]，如果dp[i]<0，则令dp[i] = 0，舍去前面的解
最后ans = max{dp[i]}，1≤i≤N，其中也可以用类似滚动数组的方法优化，将dp[]数组转为只用一个变量表示，ans的值在每次去最大即可
最大子矩阵
poj1050的原型，目前会的方法是用一个数组b[k][j]记录第k列前j行的数的总和，方便之后O(1)的时间求出确定列指定行间的数和
枚举初始行i和结束行j，将这个一列当成一个元素，就可以像求最大连续子段和类似，求解i～j行间的一个最大子矩阵和，代码如下（N年前的，先凑合看吧）：
View Code
1 #include<cstdio> 2 #include<cstdlib> 3 4 int main (){ 5 int a[110][110]; 6 int b[110][110]={0};//第k列前j行 7 int n; 8 int i, j, k; 9 int s , max1, max=0; 10 scanf("%d",&n); 11 for (i=0;i<=n-1;i++) 12 for (j=0;j<=n-1;j++) 13 scanf("%d",&a[i][j]); 14 15 for (i=0;i<=n-1;i++){ 16 for (j=i+1;j<=n;j++){ //枚举的初始行i和结束行j 17 max1=0; s=0; 18 for (k=0;k<=n-1;k++){ 19 b[k][j] = b[k][j-1]+a[j-1][k]; //求出b[k][j] 20 s += b[k][j]-b[k][i]; //s相当于是记录和的 21 if (s<0) 22 s = 0; 23 if (s>max1) 24 max1 = s; //max1表示i～j行见的最大值 25 } 26 if (max1>max) 27 max = max1; //max表示总的最大值，即结果 28 } 29 } 30 printf("%d\n",max); 31 return 0; 32 }
最大体积块
这个没找着题，自己也没写过，应该也是要先预处理出来几个数组方便简单求和，然后转换为求最大子矩阵或直接转换为求最大子段和的问题求解，写起来挺难的，遇上在用这个思路想吧
【ps】现在来补各种简单贴发现自己弱爆了