具有整数的数组的最大子数组

Question

在一次采访中,我的一个朋友被要求找到一个具有最大总和的数组的子阵列,这是我对问题的解决方案,我如何改进解决方案使其更加优化,我是否应该考虑以递归的方式进行？

def get_max_sum_subset(x):
        max_subset_sum = 0
        max_subset_i = 0
        max_subset_j = 0
        for i in range(0,len(x)+1):
            for j in range(i+1,len(x)+1):
                current_sum = sum(x[i:j])
                if current_sum > max_subset_sum:
                    max_subset_sum = current_sum
                    max_subset_i = i
                    max_subset_j = j
        return max_subset_sum,max_subset_i,max_subset_j

Answer 1

你的解决方案是O(n ^ 2).最佳解决方案是线性的.它的工作原理是您从左到右扫描数组,记下最佳总和和当前总和:

def get_max_sum_subset(x):
    bestSoFar = 0
    bestNow = 0
    bestStartIndexSoFar = -1
    bestStopIndexSoFar = -1
    bestStartIndexNow = -1
    for i in xrange(len(x)):
        value = bestNow + x[i]
        if value > 0:
            if bestNow == 0:
                bestStartIndexNow = i
            bestNow = value
        else:
            bestNow = 0

        if bestNow > bestSoFar:
            bestSoFar = bestNow
            bestStopIndexSoFar = i
            bestStartIndexSoFar = bestStartIndexNow

    return bestSoFar, bestStartIndexSoFar, bestStopIndexSoFar

在编程珍珠:算法设计技术(强烈推荐)中也讨论过这个问题.在那里你还可以找到一个递归解决方案,它不是最优的(O(n log n)),但优于O(n ^ 2).

Answer 2

这是一个众所周知的问题,显示重叠的最佳子结构,这表明动态编程(DP)解决方案.虽然DP解决方案通常非常棘手(至少我认为如此!),但这个解决方案是一个很好的例子,可以介绍整个概念.

首先要注意的是,在位置j结束的最大子阵列(必须是给定数组A的连续部分)或者由位于j-1位置加上A [j]的最大子阵列组成,或者是空的(这个仅在A [j] <0时出现.换句话说,我们要问的是元素A [j]是否对当前在位置j-1结束的最大和有贡献.如果是,请将其包含在最大子阵列中; 如果没有,不要.因此,通过解决重叠的较小子问题,我们可以构建最优解.

然后,可以通过以下关系递归地给出在位置j处结束的最大子阵列的总和:

sum[0] = max(0, A[0])
sum[j] = max(0, sum[j-1] + A[j])

我们可以通过从左到右扫描A,以自下而上的方式建立这些答案.我们考虑A [j]时更新sum [j].我们也可以通过这个过程跟踪最大子阵列的总体最大值和位置.这是我在Ruby中写的一个快速解决方案:

def max_subarray(a)
    sum = [0]
    max, head, tail = sum[0], -1, -1
    cur_head = 0

    (0...a.size).each do |j|
        # base case included below since sum[-1] = sum[0]
        sum[j] = [0, sum[j-1] + a[j]].max
        cur_head = j if sum[j-1] == 0
        if sum[j] > max
            max, head, tail = sum[j], cur_head, j
        end
    end

    return max, head, tail
end

如果您想亲自测试一下,请看看我的要点.

这显然是线性O(N)算法,因为只需要通过列表一次.希望这可以帮助!

Answer 3

通过考虑最大和子子数组必须包含的条件,可以得出更好的解决方法:任一端的第一项(未包括)(如果有的话)必须是负数,而任何一端的最后一项必须是包括在内必须是非负面的.除了原始数据中发生这些更改之外,您不需要考虑子数组的任何其他端点.

Answer 4

让n- 元素计数，a(i)- 您的数组f(i)- 在位置结束的子数组的最大总和i（最小长度为 1）。然后：

f(0) = a(i);
f(i) = max(f(i-1), 0) + a(i); //f(i-1) when we continue subarray, or 0 - when start at i position

max(0, f(1), f(2), ... , f(n-1)) - 答案