在接受记者采访时我的一个朋友被要求找到最大和数组的子数组，这是我解决问题的办法，我怎么能改进解决方案，使其更优化，要我宁可考虑做一个递归的方式？

 高清get_max_sum_subset（X）：
        max_subset_sum = 0
        max_subset_i = 0
        max_subset_j = 0
        因为我在范围（0，len个（X）+1）：
            对于在范围Ĵ第（i + 1，的len（x）的1）：
                current_sum = SUM（X [I：J]）
                如果current_sum＆GT; max_subset_sum：
                    max_subset_sum = current_sum
                    max_subset_i = I
                    max_subset_j = j的
        返回max_subset_sum，max_subset_i，max_subset_j
 

解决方案

您的解决方案是O（n ^ 2）。最优解是线性的。它的工作原理，以便在扫描阵列，从左至右，注意到最好总和和当前总和：

 高清get_max_sum_subset（X）：
    bestSoFar = 0
    bestNow = 0
    bestStartIndexSoFar = -1
    bestStopIndexSoFar = -1
    bestStartIndexNow = -1
    对我的xrange（LEN（X））：
        值= bestNow + X [I]
        如果值GT; 0：
            如果bestNow == 0：
                bestStartIndexNow = I
            bestNow =价值
        其他：
            bestNow = 0

        如果bestNow＆GT; bestSoFar：
            bestSoFar = bestNow
            bestStopIndexSoFar = I
            bestStartIndexSoFar = bestStartIndexNow

    返回bestSoFar，bestStartIndexSoFar，bestStopIndexSoFar
 

这个问题也是在Programming珍珠：算法设计技术（强烈推荐）。在那里，你还可以找到一个递归的解决方案，这是不是最佳的（为O（n log n）的），但为O更好的（N ^ 2）。

In an interview one of my friends was asked to find the subarray of an array with maximum sum, this my solution to the problem , how can I improve the solution make it more optimal , should i rather consider doing in a recursive fashion ?

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

Your solution is O(n^2). The optimal solution is linear. It works so that you scan the array from left to right, taking note of the best sum and the current sum:

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

This problem was also discussed thourougly in Programming Pearls: Algorithm Design Techniques (highly recommended). There you can also find a recursive solution, which is not optimal (O(n log n)), but better than O(n^2).