Tag: kadanes算法

n个数字排成一个圆圈。 我们需要找到连续nos的最大总和

对于线性arrays，找到连续nos的最大总和的问题。 简单。 可以通过使用Kadane的Algo轻松完成。 。 但是现在arrays是圆形的，我们需要找到连续nos的最大总和。 因此startindex和endindex可以在数组中的任何位置。 我没有得到如何在O(n)时间内解决它。 例如： { 8, 9, -14, 4, 3} 。 最大子arrayssum= 4+3+8+9= 24. startindex=3 and endindex=1 （零索引数组）。 请给我一些关于如何处理这个问题的提示或算法。 无需代码。 编辑：正如大家所提到的，圆形数组类似于跨越两次的相同数组。 但是如何在该arrays上应用Kadane的Algo并限制连续的nos。 到<= n

如何在Kadane的算法中返回最大子数组？

public class Kadane { double maxSubarray(double[] a) { double max_so_far = 0; double max_ending_here = 0; for(int i = 0; i < a.length; i++) { max_ending_here = Math.max(0, max_ending_here + a[i]); max_so_far = Math.max(max_so_far, max_ending_here); } return max_so_far; } } 上面的代码返回最大子数组的总和。 我怎样才能返回具有最大总和的子数组？