題目地址： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1074
這道題的dP是基于 “最大子段和” 的dp方法
例如求數組 ?1 ?2 ?-3 ?4；-5 ?6 ?-1 ?8 的最大子矩陣和，可以把兩行相加得到數組-4 ?8 ?-4 ?12，對這個數組求最大子段和為8+-4+12=16，所以矩陣對應的最大子矩陣為2 ?-3 ?4；?6 ?-1 ?8
那么可以利用以上思想，對于m*n的矩陣A，選取他的第 i 行到第 j 行的數據組成子矩陣Aij (j-i+1行n列)，Aij 對應的最大子段和可以如下求得：對每一列的值進行累加得到一個一維數組(1*n)，對該數組求最大字段和（ 其中 ?1=< i=<j<=m ）。
綜上所述，A的最大子矩陣和為：max（ subMatrix(Aij) ） ，其中1=< i=<j<=m ，subSegment(Aij) 表示Aij?對應的最大子段和。
?
上代碼：
1
#include<iostream>
2
#include <cstring>
3
using
namespace
std;
4
5
int
maxSubSegment(
int
*arr,
int
n)
6
{
7
int
max=-
65535
,sum=
0
;
8
for
(
int
i=
1
;i<=n;i++
)
9
{
10
if
(sum>
0
)sum+=
arr[i];
11
else
sum=
arr[i];
12
if
(max<sum)max=
sum;
13
}
14
return
max;
15
}
16
17
int
matrix[
101
][
101
];
18
int
sum[
101
];
19
int
main()
20
{
21
int
N;
22
cin>>
N;
23
24
for
(
int
i=
1
;i<=N;i++
)
25
for
(
int
j=
1
;j<=N;j++
)
26
{
27
cin>>
matrix[i][j];
28
}
29
////////////////////////
//Dp;
30
int
result=-
65535
;
31
for
(
int
i=
1
;i<=N;i++
)
32
{
33
memset(sum,
0
,
sizeof
(sum));
34
for
(
int
j=i;j<=N;j++
)
35
{
36
for
(
int
k=
1
;k<=N;k++
)
37
sum[k]+=
matrix[j][k];
38
int
re=
maxSubSegment(sum,N);
39
if
(result<
re)
40
result=
re;
41
}
42
}
43
cout<<
result;
44
return
0
;
45
}
?【版權聲明】轉載請注明出處? http://www.cnblogs.com/TenosDoIt/archive/2013/04/16/3025007.html
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
