n个数被设置成圆形。我们需要找到的连续号的最大总和 [英] n numbers are arranged in a circle. We need to find the maximum sum of consecutive nos

问题描述

有关的线性阵列，发现连续号的最大总和的问题。简单。可以通过使用 Kadane的算法中。轻松完成。但现在的阵列是圆的表格，我们需要找到的连续号的最大总和。所以startIndex和endIndex，可以在阵列中的任何地方。我没有得到如何解决它 O（N）的时间。

For a linear array, the problem of finding maximum sum of consecutive nos. is easy. Can be easily done by using Kadane's Algo.. But now the array is in the form of circle and we need to find the maximum sum of consecutive nos. So the startindex and endindex can be anywhere in the array. I am not getting how to solve it in O(n) time.

例如： {8，9，14日，4，3}

最大子阵和= 4 + 3 + 8 + 9 = 24，则startindex = 3和endIndex = 1 （零数组索引）。
请给我对如何处理这个问题的一些提示或算法中。无需code。

Maximum subarray sum= 4+3+8+9= 24. startindex=3 and endindex=1 (zero index array). Please give me some hint or algo on how to approach this problem. No code required.

编辑：大家都提到的，圆阵类似于同一阵列跨越两次。但如何应用Kadane的算法中的阵列上，并限制连续号。到＆lt; = N

As everyone mentioned, a circular array is similar to same array spanning twice. But how to apply Kadane's Algo on that array and restricting the consecutive nos. to <=n

推荐答案

或者，而不是复制数组，从 0到n-1 到 0..2n-1 ，并使用（X MOD N）而不是 X 作为索引。

Or, rather than copy the array, extend the range of the index variable from 0..n-1 to 0..2n-1 and use (x mod n) instead of x as the index.

这篇关于n个数被设置成圆形。我们需要找到的连续号的最大总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！