graph - 算法：返回最大和的子图

Question

给定一个连通图，每个节点都有一个整数（正或负），如何找出节点值之和为最大值的子图？

在一个简化的情况下，如果这个图是一个线性链表，那么问题就变成了“返回一维数组中的子数组，其中子数组的总和最大”。我们知道存在一个 O(n) 解。

为了让我的问题更简单，我们假设每个节点不能超过 4 条边。

我看过一些图算法，但没有找到确切的解决方案。

Answer 1

由于您对子图的结构没有任何限制，因此只需删除具有负值的节点即可。这总是会产生具有最大节点总和的子图。