29

我对这个问题试图提出的问题感到困惑。

编写mssl()将整数列表作为输入的函数（最小和子列表）。然后它计算并返回输入列表的最大和子列表的总和。最大和子列表是输入列表的条目总和最大的子列表（切片）。空子列表的总和定义为 0。例如，列表的最大总和子列表[4, -2, -8, 5, -2, 7, 7, 2, -6, 5]是[5, -2, 7, 7, 2] ，其条目的总和是19。

如果我要使用这个函数，它应该返回类似于

>>> l = [4, -2, -8, 5, -2, 7, 7, 2, -6, 5]
>>> mssl(l)
19
>>> mssl([3,4,5])
12
>>> mssl([-2,-3,-5])
0

我该怎么做？

这是我目前的尝试，但它不会产生预期的结果：

def mssl(x):
    ' list ==> int '
    res = 0
    for a in x:
        if a >= 0:
            res = sum(x)
        return res
    else:
        return 0
4

13 回答 13

55

实际上有一个使用动态编程的非常优雅、非常有效的解决方案。它需要O(1) 空间和O(n) 时间- 这是无法击败的！

定义A为输入数组（零索引），并且B[i]是所有以位置结尾但不包括位置i（即所有子列表A[j:i]）的子列表的最大总和。因此 ,B[0] = 0和B[1] = max(B[0]+A[0], 0), B[2] = max(B[1]+A[1], 0), B[3] = max(B[2]+A[2], 0), 等等。然后，很明显，解决方案由 简单地给出max(B[0], ..., B[n])。

由于每个B值只依赖于前一个B，我们可以避免存储整个B数组，从而为我们提供 O(1) 空间保证。

使用这种方法，mssl可以简化为一个非常简单的循环：

def mssl(l):
    best = cur = 0
    for i in l:
        cur = max(cur + i, 0)
        best = max(best, cur)
    return best

示范：

>>> mssl([3,4,5])
12
>>> mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5])
19
>>> mssl([-2,-3,-5])
0

如果您还想要开始和结束切片索引，则需要跟踪更多信息位（注意这仍然是 O(1) 空间和 O(n) 时间，只是有点毛茸茸）：

def mssl(l):
    best = cur = 0
    curi = starti = besti = 0
    for ind, i in enumerate(l):
        if cur+i > 0:
            cur += i
        else: # reset start position
            cur, curi = 0, ind+1

        if cur > best:
            starti, besti, best = curi, ind+1, cur
    return starti, besti, best

这将返回一个元组(a, b, c)，使得sum(l[a:b]) == c和c是最大的：

>>> mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5])
(3, 8, 19)
>>> sum([4, -2, -8, 5, -2, 7, 7, 2, -6, 5][3:8])
19
于 2013-02-25T09:06:07.893 回答
7

这就是最大子阵问题。Kadane的算法可以在O(n)时间和O(1)空间上解决它，它是这样的：

def mssl(x):
    max_ending_here = max_so_far = 0
    for a in x:
        max_ending_here = max(0, max_ending_here + a)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far
于 2013-02-26T07:30:07.297 回答
4

根据问题，如果列表中的所有元素均为负数，则应将最大总和返回为“零”

相反，如果您希望输出为子数组的最大值（负数），则以下代码将有所帮助：

In [21]: def mssl(l):
...:     best = cur = l[0]
...:     for i in range(len(l)):
...:         cur = max(cur + l[i], l[i])
...:         best = max(best, cur)
...:     return best

例子：

In [23]: mssl([-6, -44, -5, -4, -9, -11, -3, -99])
Out[23]: -3
In [24]: mssl([-51, -23, -8, -2, -6])
Out[24]: -2

对于正数和负数

In [30]: mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5])
Out[30]: 19
于 2017-09-08T09:46:41.073 回答
3

因此，如果您了解什么是子列表（或切片，可以假定为同一事物），则切片由开始索引和结束索引定义。

因此，也许您可​​以尝试遍历所有可能的开始和结束索引并计算相应的总和，然后返回最大值。

提示：起始索引可以从 0 到len(given_list)-1. 结束索引可以是 fromstart_index到len(given_list)-1。您可以使用嵌套for循环来检查所有可能的组合。

于 2013-02-25T08:36:20.773 回答
3

这是 Java 中的一个实现，使用 Kadane 的算法，它打印最大和的索引。该实现需要 O(n) 时间和 O(1) 空间。

public static void maxSumIndexes(int[] a) {

    int size = a.length;
    if(size == 0) return;

    int maxAtIndex = a[0], max = a[0];
    int bAtIndex = 0;
    int b = 0, e = 0;

    for(int i = 1; i < size; i++) {
        maxAtIndex = Math.max(a[i], a[i] + maxAtIndex);
        if(maxAtIndex == a[i])
            bAtIndex = i;

        max = Math.max(max, maxAtIndex);
        if(max == maxAtIndex) {
            e = i;
            b = (b != bAtIndex)? bAtIndex : b;
        }
    }

    System.out.println(b);
    System.out.println(e);
}
于 2014-11-25T10:00:02.520 回答
2

简单的解决方案是遍历列表，然后尝试将切片相加，直到找到最好的切片。在这里，我还包括返回实际子列表的选项，默认情况下这是 False。我为此目的使用了 defaultdict，因为它比查找更简单。

from collections import defaultdict

def mssl(lst, return_sublist=False):
    d = defaultdict(list)
    for i in range(len(lst)+1):
        for j in range(len(lst)+1):
            d[sum(lst[i:j])].append(lst[i:j])
    key = max(d.keys())
    if return_sublist:
        return (key, d[key])
    return key

print mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5])
19
print mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5], True)
(19, [[5, -2, 7, 7, 2]])

奖励：列表理解方法：

def _mssl(lst):
    return max( sum( lst[i:j] ) for i in xrange(len(lst)+1) for j in xrange(i, len(lst)+1) )
于 2013-02-25T08:37:59.803 回答
1

我假设这是在产生最大和的数组中找到子序列的问题。我在搜索最大和 SUBSET 问题时遇到了这个问题。

这个问题的java实现：

public static int maximumSumSubSequence(int[] array) {

    if (null == array) {
        return -1;
    }

    int maxSum = Integer.MIN_VALUE;
    int startIndexFinal = 0;
    int endIndexFinal = 0;
    int currentSum = 0;
    int startIndexCurrent = 0;

    for (int i = 0; i < array.length; i++) {
        currentSum += array[i];

        if (currentSum > maxSum) {
            maxSum = currentSum;
            endIndexFinal = i;
            startIndexFinal = startIndexCurrent;
        }
        if (currentSum <= 0) {
            currentSum = 0;
            startIndexCurrent = i + 1;
        }
    }
    System.out.println("startIndex: " + startIndexFinal + " endIndex: " + endIndexFinal);
    return maxSum;
}
于 2014-11-02T16:41:08.507 回答
1

它要求您选择列表的较小部分，以使较小部分的总和最大。

如果列表都是正数[1 2 3]，那么总和最大的子部分当然就是整个列表的总和，[1 2 3]即 6。

如果列表都是负数[-1 -2 -3]，那么总和最大的小节就是总和为[]0 的无。

但是，如果列表有一些正面和一些负面的决定，那就更难了

[1 2 3 -100 3 4 5]你应该看到[3 4 5]并返回 12

[1 2 3 -2 3 4 5]你应该使用它并返回 16

于 2013-02-25T08:35:37.477 回答
0

这种区别对 OP 来说可能并不重要，他似乎只是想了解如何解决问题，但我认为值得一提：

这里的其他解决方案涉及重复总结列表的所有子部分。我们可以通过使用动态编程来避免这些重复的总和，因为当然，如果我们已经知道从i到的总和，j我们不需要再次将它们相加来得到从i到的总和j+1！

也就是说，制作部分和的二维数组，这样partsum[i, j] == sum(lst[i:j]). 类似的东西（使用字典，因为它更容易索引；一个 numpy 数组同样容易且更有效）：

import operator

def mssl(lst, return_sublist=False):
    partsum = { (0, 0): 0 }  # to correctly get empty list if all are negative
    for i in xrange(len(lst) - 1):  # or range() in python 3
        last = partsum[i, i+1] = lst[i]
        for j in xrange(i+1, len(lst)):
            last = partsum[i, j+1] = last + lst[j]

    if return_sublist:
        (i, j), sum = max(partsum.iteritems(), key=operator.itemgetter(1))
        return sum, lst[i:j]

    return max(partsum.itervalues())  # or viewvalues() in 2.7 / values() in 3.x

这需要 O(n^2) 时间和内存，而 Lev/Inbar 的方法需要 O(n^3) 时间和 O(1) 内存（如果没有像 Inbar 的第一个代码示例那样愚蠢地实现）。

于 2013-02-25T08:57:19.480 回答
0

我正在介绍一种基于动态编程的方法。主要思想是，当我们遍历数组时，向我们当前的 sum-value 添加一个新元素应该增加 sum 的值，或者，我们继续使用当前元素并忘记旧的 sum-value。

为了适应具有负值的数组，我们用数组的第一个元素实例化我们的变量。

def maxSumSubArr(arr):
    cur_sum = best_sum = arr[0]
    for i in range(1, len(arr)):
        cur_sum = max(arr[i], cur_sum+arr[i])
        best_sum = max(best_sum, cur_sum)
    return best_sum

该方法的运行时间为O(n)，空间复杂度为O(1)。

如果您希望在没有任何元素为正的情况下输出为零，则使用 0 实例化 cur_sum 和 best_sum 变量，并从第一个元素而不是第二个元素进行迭代。

于 2018-12-13T01:06:44.997 回答
0

这篇文章介绍了三种方法来找到数组的最大子数组。

  • 蛮力 (O(n*n))
  • 分而治之 (O(nlgn))
  • Kadane 算法 (O(n))

其中，最快的是时间复杂度为 O(n) 的 Kadane 算法。

于 2015-07-20T15:54:04.980 回答
0

这是 javascript 中最大子数组问题的最短和最佳解决方案：

var maxSubArray = function(nums) {
    for (let i = 1; i < nums.length; i++){
        nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]);
    }
    return Math.max(...nums);
};
于 2019-08-08T16:28:52.827 回答
0

如果有人正在寻找更长版本的代码，这里是：

def mesl(lst):
    sub_sum = list()
    row_sum = list()
    for i in range(len(lst)):
        sub_sum = list()
        sub_sum.append(lst[i])
        k = 1
        for j in range(i+1,len(lst)):
            sub_sum.append(sub_sum[k-1] + lst[j])
            k+=1
        row_sum.append(max(sub_sum))      
    sum = max(row_sum)
    if  sum < 0:
        sum = 0
    return sum
于 2016-10-02T10:01:53.563 回答