arrays - 这是图形问题还是其他问题？

Question

我遇到了一个问题，起初看起来像众所周知的最大和子数组问题，但有一个转折使事情变得更加复杂。

假设您有两个数组，每个数组都包含相同数量的“1”和“-1”。此外，假设第一个数组中的每个“1”在第二个数组中都有一个对应的或同级的“1”。每个“-1”都相同。任务是找到最佳子数组，一个在第一个数组中，一个在第二个数组中，这样它们的组合总和是最大的（最大），并增加了一个约束，即一个子数组中的元素仅计入总和，如果另一个子数组包含它的兄弟。

有谁知道这是什么问题？看起来这可能是一个变相的图形问题，但我不确定是哪个。如果这里有最佳子结构，我也看不到。我知道它可以通过完整的搜索来解决，但肯定有更快的方法。

以下是问题设置的示例。

这里的最佳解决方案是第一个数组中的子数组 [2..9] 和第二个数组中的子数组 [4..9]，总和为 8。

标签： arraysalgorithmoptimizationgraph-algorithm