最大总和子列表？

编程入门行业动态更新时间:2024-10-14 04:23:47

本文介绍了最大总和子列表？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！问题描述

我越来越糊涂了这个问题，在什么它试图问。

Write函数社会保障和（）（最小和子列表），它作为输入列表的整数。然后，它计算并返回最大总和的总和子列表中的输入列表。的最大总和子列表是一个子表输入列表中的条目的总和是最大的（切片）。空子列表被定义为具有总和0。例如，最大总和子列表列表 [4，-2，-8，5，-2，7,7，2，-6，5] 是 [5 ，-2，7,7，2] 其项之和 19 。

如果我要使用此功能，应该返回类似的东西。

＆GT;＆GT;＆GT;升= [4，-2，-8，5，-2，7,7，2，-6，5] ＆GT;＆GT;＆GT;社会保障和（L） 19 ＆GT;＆GT;＆GT;社会保障和劳工部（[3,4,5]） 12 ＆GT;＆GT;＆GT; MSSL（[ - 2，-3，-5]） 0

我该怎么办呢？

下面是我目前的尝试，但它并没有产生预期的结果：

DEF社会保障和劳工部（X）：名单==＆GT; INT RES = 0 对于在X：如果a取代; = 0： RES = SUM（X）回报水库其他：返回0

解决方案

目前实际上使用的是非常优雅，非常有效的解决方案的动态规划的。它需要的 O（1）空间和 O（n）的时间 - ！这不能被打败

定义 A 是输入数组（零索引）和 B [I] 为最大总结以上是结束，但不包括位置所有子列表我（即所有子列表 A [J：我] ）。因此， B [0] = 0 和 B [1] = MAX（B [0] + A [0]，0）， B [2] = MAX（B [1] + A [1]，0）， B [3] =最大值（B [2] + A [2]，0），系统等。那么，显然，解决的方法就是通过给予最大（B [0]，...，B [N]）。

由于每个 B 的价值仅仅依赖于previous B ，可避免储存整个 B 阵列，从而给我们我们的O（1）空间的保证。

通过这种方法，社会保障和降低到一个非常简单的循环：

DEF社会保障和（L）：最好= CUR = 0 因为我在L： CUR = MAX（当前+ I，0）最好= MAX（最佳，CUR）返回最佳

演示：

＆GT;＆GT;＆GT;社会保障和劳工部（[3,4,5]） 12 ＆GT;＆GT;＆GT; MSSL（[4，-2，-8，5，-2，7,7，2，-6，5]） 19 ＆GT;＆GT;＆GT; MSSL（[ - 2，-3，-5]） 0

如果你想要的开始和结束切片指数，也一样，你需要跟踪几个比特的信息（注意，这仍然是O（1）空间和O（n）的时间，它只是有点多毛）：

DEF社会保障和（L）：最好= CUR = 0 CURI = starti = besti = 0 对于IND，我历数（1）：如果CUR + I＆GT; 0： CUR + = I 其他：＃重新启动位置 CUR，CURI = 0，IND + 1 如果CUR＆GT;最好成绩： starti，besti，最好= CURI，IND + 1，CUR 返回starti，besti，最佳

这会返回一个元组（A，B，C），使得和（L [A：B]）==ç和 C 是最大的：

＆GT;＆GT;＆GT; MSSL（[4，-2，-8，5，-2，7,7，2，-6，5]）（3，8，19）＆GT;＆GT;＆GT;总和（[4，-2，-8，5，-2，7,7，2，-6，5] [3：8]） 19

I'm getting confused with this question at what it's trying to ask.

Write function mssl() (minimum sum sublist) that takes as input a list of integers. It then computes and returns the sum of the maximum sum sublist of the input list. The maximum sum sublist is a sublist (slice) of the input list whose sum of entries is largest. The empty sublist is defined to have sum 0. For example, the maximum sum sublist of the list [4, -2, -8, 5, -2, 7, 7, 2, -6, 5] is [5, -2, 7, 7, 2] and the sum of its entries is 19.

If I were to use this function it should return something similar to

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

How can I do it?

Here is my current try, but it doesn't produce the expected result:

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

解决方案

There's actually a very elegant, very efficient solution using dynamic programming. It takes O(1) space, and O(n) time -- this can't be beat!

Define A to be the input array (zero-indexed) and B[i] to be the maximum sum over all sublists ending at, but not including position i (i.e. all sublists A[j:i]). Therefore, B[0] = 0, and B[1] = max(B[0]+A[0], 0), B[2] = max(B[1]+A[1], 0), B[3] = max(B[2]+A[2], 0), and so on. Then, clearly, the solution is given simply by max(B[0], ..., B[n]).

Since every B value depends only on the previous B, we can avoid storing the whole B array, thus giving us our O(1) space guarantee.

With this approach, mssl reduces to a very simple loop:

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

Demonstration:

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

If you want the start and end slice indices, too, you need to track a few more bits of information (note this is still O(1) space and O(n) time, it's just a bit hairier):

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

This returns a tuple (a, b, c) such that sum(l[a:b]) == c and c is maximal:

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