九度OJ; 题目1139：最大子矩阵

?

简单说明下思路

如果不会最大子数组的人，请先查看最大子数组如何求解再看本文；

?

本文最容易相到的思路是直接暴力，但是很明显会超时，那么就会想到用动态规划了，然后这个题目的子问题是什么，确实是一个比较难以想到的问题。

本文的思路是：我先假定我的最优解在第i行开始，此时就确定了开始行，然后再假设在j行结束，最后就需要确定列的起始位置了。

我们先看看i-j的时候，这个问题会不会求解：

从i行到j行，此时，只需要确定列的起始和结束位置，和行无关，则只需要讲i-j行相加，就得到了最大子数组的问题了；

到这里就发现，固定i的时候，对于j=i到j=n的问题都可以解决，即，找到了子问题。

result=max{max {maxArray(i,j),j>=i&&j =0,i

?

#include 
  
   
#include 
   
     int maxSubArray(int A[101],int n) { int result=A[0],b=0; for(int i=0;i
    
     0) b=b+A[i]; else b=A[i]; if(b>result) result=b; } return result; } int main() { //freopen(data.in,r,stdin); int n,A[101][101],result,tmp[101]; while(scanf(%d,&n)!=EOF) { memset(A,0,sizeof(A)); for(int i=0;i
     
      result) result=tmsSubarray; } } printf(%d ,result); } return 0; } /************************************************************** Problem: 1139 User: vincent_ynh Language: C++ Result: Accepted Time:60 ms Memory:1020 kb ****************************************************************/ 
     
    
   
  

?