<ins id="pjuwb"></ins>

<blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

<noscript id="pjuwb"></noscript>

<sup id="pjuwb"><pre id="pjuwb"></pre></sup>

<dd id="pjuwb"></dd>

<abbr id="pjuwb"></abbr>

poj1050To the Max_最大子段和

題意：
求給定矩陣的最大子矩陣和。
先來回顧一下一維的最大子段和問題：
給定一個序列a[n]，求a[n]的最大子段和。
DP的遞推公式為b[j] = max{b[j - 1] + a[j], a[j]}. 其中b[j]表示a[n]中包含b[j]的最大子段和。時間復(fù)雜度為O(n)
對于二維矩陣而言，我們可以通過把多行壓縮（按列求和）成一行的方式將問題轉(zhuǎn)換為一維。
行壓縮時枚舉復(fù)雜度為O(N^2)。因此整個求解過程的時間復(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) 閱讀(298) 評論(0) 編輯收藏引用所屬分類: Java基礎(chǔ)練習(xí)

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

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

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

2013年4月

日

一

二

三

四

五

六

31

1

2

5

7

8

10

11

12

13

15

19

20

21

22

23

24

25

26

27

29

1

2

3

4

5

6

7

8

9

10

11

常用鏈接

隨筆分類(111)

隨筆檔案(127)

friends

陳鋼
大鵬
黨姐
焦林楓
汪濤
小白學(xué)長
媛姐
媛姐csdn

最新評論

1.?re: 線段樹
是這個樣子的，所以在OJ有時候“卡住”了也不要太灰心，沒準(zhǔn)真的不是自己的原因呢。
加油，祝你好運啦！
--小鼠標(biāo)
2.?re: 線段樹
對于編程競賽來說，Java所需時間一般為C/C++的兩倍。合理的競賽給Java的時間限制是給C/C++的兩倍。
--傷心的筆
3.?re: poj1273--網(wǎng)絡(luò)流
過來看看你。
--achiberx
4.?re: （轉(zhuǎn)）ubuntu11.10無法啟動無線網(wǎng)絡(luò)的解決方法
膜拜大神。。查了一個下午資料終于在這里解決了問題。。神牛說的區(qū)域賽難道是ACM區(qū)域賽。。？
--Hang
5.?re: 快速排序、線性時間選擇
博主，謝謝你的文章。你的方法可以很好的處理分區(qū)基準(zhǔn)在數(shù)組中重復(fù)的情況，書上的方法遇到這種輸入會堆棧溢出。書上給出了解釋但給的方法貌似不簡潔。
--lsxqw2004

閱讀排行榜

久久成人国产精品| 国产精品18久久久久久vr | 国产精品美女久久福利网站| 精品久久久久久99人妻| 亚洲国产天堂久久综合网站| a级毛片无码兔费真人久久| 国产精自产拍久久久久久蜜| 久久伊人五月天论坛| 亚洲中文字幕久久精品无码APP| 久久久久久人妻无码| 69久久精品无码一区二区| 久久精品国产精品亚洲人人 | 精品久久久久久99人妻| 久久天天日天天操综合伊人av| 伊人热热久久原色播放www| 久久久久亚洲精品无码蜜桃| 青青草国产精品久久| 久久亚洲精品成人无码网站| 国产精品无码久久综合| 久久天天躁狠狠躁夜夜不卡 | 久久99精品久久久久久噜噜| 久久久亚洲AV波多野结衣| 久久国产欧美日韩精品| 久久久久99精品成人片牛牛影视| 亚洲成色WWW久久网站| 性做久久久久久久久| 中文字幕一区二区三区久久网站| 久久亚洲精品国产亚洲老地址| 青青草原综合久久| 久久亚洲私人国产精品vA| 久久久久无码专区亚洲av| 久久青草国产精品一区| 亚洲∧v久久久无码精品| 久久精品人妻一区二区三区| 久久最近最新中文字幕大全| 青草国产精品久久久久久| 中文字幕精品久久| 亚洲精品tv久久久久| 久久精品国产亚洲一区二区三区| 日韩亚洲欧美久久久www综合网 | 欧美亚洲国产精品久久久久|