在一次采访中，我的一位朋友被要求找到最大和的数组的子数组，这是我对问题的解决方案，如何改善解决方案使其更优化，我是否应该考虑以递归方式进行？
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
您的解决方案是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
在“ PearsPearls：算法设计技术”（强烈推荐）中也对这个问题进行了详尽的讨论。在这里您还可以找到一个递归解，它不是最优的（O（nlog n）），但是比O（n ^ 2）好。
