最大圆形子阵列总和

Question

这是Jeff Erickson的书籍算法的问题。

假设a是圆形阵列。在此设置中，“连续子阵列”可以是间隔a [i .. j]或后缀，后跟前缀a [i .. n]·a [1 .. j]。描述和分析一个找到具有最大总和的连续子阵列的算法。 输入阵列由实数组成。

我的方法：

有两种可能性

1.）没有包装（我们可以使用Kadane的算法）

2.）包裹周围（即，子阵列的起始索引大于结束索引）（在这种情况下，我怀疑）

现在返回结果最多两种情况。

对于第二种情况，在互联网上搜索提供了一种没有证据的方法。

方法是找到具有最小和总和的子阵列，并从整个阵列的总和中减去它（即SUM（a） - min_subarray_sum（a））。这个解决方案如何正确？

用于第二个案例中使用的方法的链接： https：// www。 geeksforgeeks.org/maximum-contiguous-circular-sum/

Answer 1

let $ a $ 是您的数组，让 $ b $ $ a $ ，最大化 $ \ sum_ {b \ in b} b $ ，并让 $ C $ 包含包含 $ a $ 的所有元素的子阵列，它不在> $ b $ 。请注意， $ c $ 也是圆形子阵列。

您有 $ \ sum_ {a \在a}} b + \ sum_ {b \ in c} c $ ，这意味着 $ \ sum_ {c \中的c} c=sum_ {a \中的a} - \ sum_ {b \中的b} b $ 。由于<跨越类=“math-container”> $ \ sum_ {a \中的a} $ 是一个常量（wrt $ b $ ）和 $ b $ 最大化 $ \ sum_ {b \ in b} b $ ， $ C $ 最小化 $ \ sum_ {c \ in c} c $ 。

此外，

而言， $ b $ 和 $ c $ 不仅是圆形的，还有一个连续的，因此可以在 $ o（n）$ 时间中找到。