首页 > 代码库 > hdu--1081--最大子矩阵和

hdu--1081--最大子矩阵和

2024-07-12 04:18:23   223人阅读

一般 做这题之前应该先去做下 hdu的1003----这是 一维上的 最大连续和

矩阵么 就是二维了嘛~

我一开始 走进了个错误的方向... 我去计算了第X行前Y个数的和...这是不对的

我们这里也同样用到了 前缀和的思想 但应该去计算前X个行第Y个数的和

这样 假如 有个matrix[j][y] - matrix[i-1][y]就是表示 第I行到第J行Y列上的和

如果 这个y我们用 0 ->n去遍历它 并且可以通过sum+=matrix[a][b] 来判断到第某行可以使和尽量最大

一共是需要O(n^3)的时间复杂度 去遍历整个矩阵 判断每个子矩阵的和 来求得最大的值

似乎没有更优化的了...   要是可以变成 一维的复杂度 那太好了

　　　　touch me

 

 1 #include <iostream> 2 using namespace std; 3  4 const int size = 110; 5 int matrix[size][size]; 6  7 int main() 8 { 9     int n , i , j , k;10     int sum , mmax , temp , num;11     while( cin>>n )12     {13         mmax = -520;14         for( i = 0 ; i<n ; i++ )15         {16             for( j = 0 ; j<n ; j++ )17             {18                 cin >> num;19                 matrix[i][j] = i>0 ? matrix[i-1][j] + num : num;20             }21         }22         for( i = 0 ; i<n ; i++ )    23         {24             for( j = i ; j<n ; j++ )25             {26                 sum = 0;27                 for( k = 0 ; k<n ; k++ )28                 {29                     if(i>0) 30                         temp = matrix[j][k] - matrix[i-1][k]; 31                     else32                         temp = matrix[j][k];33                     sum += temp;34                     if( sum>mmax )35                         mmax = sum;36                     if( sum<0 )37                         sum = 0;        38                 }39             }40         }    41         cout << mmax << endl;            42     }43     return 0;44 }45
View Code

 


联系
我们