算法：給出一個連通圖，每個節點都有一個整數（正數或負數），如何找出其中節點值的總和爲最大值的子圖的最大總和爲

在一個簡化的情況下，如果這個圖是一個線性鏈表，那麼問題就變成「返回一維數組中的子數組，其中子數組的總和最大」。我們知道存在一個O（n）獨子。

爲了讓我的問題更簡單，讓我們假設每個節點不能超過4條邊。

我曾看過一些圖算法，但還沒有找到確切的解決方案。

2013-09-28 Xin Zou

請問你能展示你的作品嗎？ – berkay

您的問題可能僅限於平面圖嗎？ – DanielV

是的，除了在節點處連接之外，邊緣彼此不交叉。 –

由於您對子圖的結構沒有任何限制，只需刪除負值的節點即可。這總是導致具有最大節點總和的子圖。

2013-10-04 18:20:12

問題是不適當的，所以我認爲這是一個公平的答案。然而，如果一個負節點是一個橋（從圖的理論意義上來說），那麼它將把圖分成兩個單獨連接的組件。我猜這不是OP想要的，但很難說清楚。 – Hooked

回答