当前位置: 首页 > 知识库问答 >
问题:

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

颜畅
2023-03-14
    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};

注意这里有一个类似的问题:在Kadane的算法中如何返回最大子数组?

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

共有1个答案

江温书
2023-03-14

由于您标记了Algorithm,所以这里有一个解释,后面是Python实现。

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

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
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]

请注意,如果您想考虑空的连续子数组,只需在末尾添加一个检查--如果全局最大值小于0,则返回一个空数组。

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

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))

这将创建带有正数和负数的随机数组,并断言输出数组的和等于常规版本的Kadane算法的输出。

 类似资料:
  • oracle DB是否能够返回时区区域,例如欧洲/伦敦,而不仅仅是偏移?我想知道服务器所在的地区名称。 从DUAL中选择SYSTIMESTAMP参数;返回日期、时间和偏移量: 从dual中选择DBTIMEZONE;返回偏移量:

  • 问题内容: 从如下所示的数组中,如何获取数组中最大值的索引。对于下面的数组,期望的结果将为‘11’。 问题答案: 我的解决方案是: 注意: 这样,您可以检索与给定 最大值 相关的 每个键 。 __ 如果您只对 其中一个键 感兴趣,只需使用 $ maxs [0]

  • 问题内容: 搜索时,Elasticsearch返回包含各种元信息的数据结构。 实际结果集包含在从数据库返回的JSON结果内的“ hits”字段中。 Elasticsearch是否有可能仅返回所需的数据(然后是“ hits”字段的内容)而没有嵌入所有其他元数据中? 我知道我可以将结果解析为JSON并提取出来,但是我不希望复杂性,麻烦和性能下降。 谢谢! 这是Elasticsearch返回的数据结构的

  • 问题内容: 我知道标题有点乱,但是我不知道如何更好地解释它。 我正在尝试做的是: 使用在文本文件中找到的图形,找到并打印从顶点A到顶点B的最短路径(最小顶点数量)。 注意:请使用广度优先搜索,而不是Dijkstra搜索。 我所拥有的: 一种有效的算法,将BFS应用于图形,但是没有实际打印出最短路径的好方法。 我很难 区分最短路径中的顶点与仅通过算法运行的顶点,而不是最短路径中的顶点。 例如:查找0

  • 问题内容: 我有这行代码(总是返回1): 其中token [“ rows”]是: 我想对组件数量进行计数。 这也不起作用: 整个JSON在这里: 问题答案: 根据您在另一个答案中的评论,我现在可以了解您为什么感到困惑。您没有在问题中提到正在执行XML到JSON的转换。 如您所知,XML不像JSON那样具有“对象”或“数组”的概念。在XML中,所有内容都只是命名节点的集合。在确定某个东西应该是数组还

  • 这是我的代码: 它读取上传的文件,并将原始文件保存在数据对象(propertiesData)中。问题就出在这一部分: console.log(readFiles);显示像这样的原始文件数组和console.log(i);显示console.log(readfiles[i])的正确索引;应该显示一个原始文件字符串,但它只显示未定义的。为什么?