题意：
求给定矩阵的最大子矩阵和。
先来回顾一下一维的最大子段和问题：
给定一个序列a[n]，求a[n]的最大子段和。
DP的递推公式为b[j] = max{b[j - 1] + a[j], a[j]}. 其中b[j]表示a[n]中包含b[j]的最大子段和。时间复杂度为O(n)
对于二维矩阵而言，我们可以通过把多行压缩（按列求和）成一行的方式将问题转换为一维。
行压缩时枚举复杂度为O(N^2)。因此整个求解过程的时间复杂度为O(N^3)。

代码
1

import java.io.*;
2

import java.util.*;
3

class Main
4

{
5

public static void main(String[] args)
7

{
8

Scanner sc = new Scanner(System.in);
10

int N;
11

N = sc.nextInt();
12

int nums[][] = new int[N][N];
13

for(int i = 0; i < N; i++)
15

{
16

for(int j = 0; j < N; j++)
17

{
18

nums[i][j] = sc.nextInt();
19

}
20

}
21

int ns[] = new int[N];
22

int max = 0;
23

for(int i = 0; i < N; i++)//begin row
24

{
25

for(int j = i; j < N; j++)// end row
26

{
27

Arrays.fill(ns, 0);
28

for(int k = 0; k < N; k++)// get ns[]
29

{
30

for(int ii = i; ii <= j; ii++)
31

{
32

ns[k] += nums[ii][k];
33

}
34

}
35

int t = thisMaxSum(ns);
36

if(t > max)
37

max = t;
38

}
39

}
40

System.out.println(max);
41

}
42

private static int thisMaxSum(int[] ns)
43

{
44

int max = 0;
45

int b = 0;
46

for(int i = 0; i < ns.length; i++)
47

{
48

if(b + ns[i] > ns[i])
49

b += ns[i];
50

else
51

b = ns[i];
52

if(b > max)
53

max = b;
54

}
55

return max;
56

}
57

}
59

posted on 2013-04-17 15:32 小鼠标阅读(265) 评论(0) 编辑收藏引用所属分类: Java基础练习

只有注册用户登录后才能发表评论。


相关文章: 编辑距离闰年判断正则表达式简单笔记 Excel格式地址转换一道模拟题——机器人行走距离计算排列练习2 素数筛法排列组合练习排列组合 poj1068Parencodings

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

2012年6月

日

一

二

三

四

五

六

常用链接

随笔分类(111)

随笔档案(127)

friends

最新评论

阅读排行榜