HooLee

If you believe, you can!

題意：
求給定矩陣的最大子矩陣和。
先來(lái)回顧一下一維的最大子段和問(wèn)題：
給定一個(gè)序列a[n]，求a[n]的最大子段和。
DP的遞推公式為b[j] = max{b[j - 1] + a[j], a[j]}. 其中b[j]表示a[n]中包含b[j]的最大子段和。時(shí)間復(fù)雜度為O(n)
對(duì)于二維矩陣而言，我們可以通過(guò)把多行壓縮（按列求和）成一行的方式將問(wèn)題轉(zhuǎn)換為一維。
行壓縮時(shí)枚舉復(fù)雜度為O(N^2)。因此整個(gè)求解過(guò)程的時(shí)間復(fù)雜度為O(N^3)。

代碼
1

import java.io.*;
2

import java.util.*;
3

class Main
4

{
5

6

public static void main(String[] args)
7

{
8

9

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

int N;
11

N = sc.nextInt();
12

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

14

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

58

}
59

posted on 2013-04-17 15:32 小鼠標(biāo) 閱讀(321) 評(píng)論(0) 編輯收藏引用所屬分類(lèi): Java基礎(chǔ)練習(xí)

只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。


相關(guān)文章: 編輯距離閏年判斷正則表達(dá)式簡(jiǎn)單筆記 Excel格式地址轉(zhuǎn)換一道模擬題——機(jī)器人行走距離計(jì)算排列練習(xí)2 素?cái)?shù)篩法排列組合練習(xí) 排列組合 poj1068Parencodings

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

<

2013年7月

>

日

一

二

三

四

五

六

30

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

常用鏈接

隨筆分類(lèi)(111)

隨筆檔案(127)

friends

最新評(píng)論

閱讀排行榜