代码之家 › 专栏 › 技术社区 › Paul C

卡丹的算法中是否保留了足够的信息来返回实际的最大子数组或索引,而不仅仅是求和?

algorithm java

Paul C · 技术社区 · 6 年前

这是Kadane算法的一个java实现,该算法用于查找具有最大和的相邻子数组的和。

    static int maxSum(int[] arr) {
        int maxEndingHere = arr[0];
        int maxGlobal = arr[0];

        for (int i = 1; i < arr.length; i++) {
            maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
            maxGlobal = Math.max(maxGlobal, maxEndingHere);
        }
        return maxGlobal;

    }

这只是返回总数。我想要真正的子阵。不过,这一信息似乎丢失了。我尝试在重置本地最大值时更新开始索引,在更新全局最大值时更新结束索引,但在这种情况下失败:

        int[] arr = {-57, -10000, -1, -4, -45, -6, -9, -19, -16, -17};

注意这里有一个类似的问题: How to return maximum sub array in Kadane's algorithm?

但据我所知,在负和的情况下,每个答案都会失败。

1 回复 | 直到 6 年前

Primusa 6 年前

自从你标记 algorithm python 实施。

这个问题是卡丹算法的直接扩展。卡丹的算法如下:

for each item in arr:
    current_max = max(current_max + item, item)
    global_max = global_max(current_max, global_max)

for each item in arr:

    # updating current max and keeping track current of start and end indices
    current_max = max(current_max + item, item)
    if item is new current_max: set current_start_index to this index
    set current_end_index to this index

    # keep track of global start and end indices
    global_max = max(global_max, current_max)
    if global_max has been updated: 
        set global_start to current_start
        set global_end to current_end

Python实现:

def maxSum(arr):

  cur_max = glob_max = float('-inf')
  glob_start = glob_end = cur_start = -1

  for index, item in enumerate(arr):

    if item > cur_max + item:
      cur_max = item
      cur_start = index
    else:
      cur_max += item

    if cur_max > glob_max:
      glob_max = cur_max
      glob_start = cur_start
      glob_end = index
  return arr[glob_start:glob_end+1]

一些测试用例:

arr = [-57, -10000, -1, -4, -45, -6, -9, -19, -16, -17]
arr = [-1, 2, -1, 20, -4, -5, -6, -9, -19, -16, -17]

输出:

[-1]
[2, -1, 20]

最后一些额外的代码来证明算法是正确的:

def kadane(arr):
  a = b = float('-inf')
  for i in arr:
    a = max(i, a+i)
    b = max(a, b)

  return b

from random import random

for _ in range(10000):
  arr = [random()-0.5 for _ in range(50)]
  assert kadane(arr) == sum(maxSum(arr))

repl.it link with code