遍历一个列表并返回n个连续值的最大和

Question

问题定义： 有N个盒子，里面有奖品或惩罚。正值 表示它是奖品，负值表示它是奖品 处罚。表示奖惩金额的N值为 作为输入传递给程序。一个人可以挑选任意数量的箱子 但这些盒子必须连续排列。程序必须打印 男子可选择的最高奖金。你知道吗

边界条件：

1<；=n<；=10^5

输入格式：

第一行包含N

第二行包含N个整数，表示用空格分隔的奖惩金额。你知道吗

输入/输出1示例：
输入：
9
2-4 4 3-2-1 7-4 3

输出：
11个

说明：
当男子选择以下五个方框4 3-2-1 7时，可获得最大奖品金额

输入/输出2示例：
输入：
20
63 78 111 43 104 -89 35 57 -55 84 111 91 -18 50 42 100 -67 84 70 63
输出：

957年

输入/输出3示例：
输入：
5
-5 -6 -8 -7 -9
输出：
0

最大执行时间限制：200毫秒

我可以解决这个问题，我的算法是正确的，但是执行时间超过了时间限制。

a=int(input())
b=list(map(int,input().split()))
e=[]
for i in range(2,a+1):
    if i!=a:
        for j in range(a-i+1):
            s=0
            for k in range(j,i+j):
                s+=b[k]
            e.append(s)
    else:
        s=0
        for k in range(a):
            s+=b[k]
        e.append(s)
print(max(e))

Answer 1

好的，这是maximum subarray sum的一个例子，你可以用kadane's算法（本质上是贪婪的）用O（n）时间复杂度来解决这个问题。你知道吗

片段：

a=int(input())
b=list(map(int,input().split()))

maximum = b[0]
sum = b[0]
for i in range(1,a):
    if sum < 0:
        sum = 0
    sum += b[i]
    maximum = max(maximum,sum)
print(maximum)

算法：

• 我们保留了两个变量，current sum和maximum，它们保存了答案。你知道吗
• 我们不断地向sum添加数组值。如果当前的sum小于0，那么我们使当前的sum等于0，然后添加更多的元素。我们这样做是因为我们希望尽可能地保持sum最大值（可能是正的）。你知道吗
• 最后，我们用它不断更新maximum值并打印maximum。你知道吗

更新：

因为这个问题涉及到奖金的收取，所以收取负金额是没有意义的。因此，唯一的变化是首先将maximum初始化为0，然后从0开始循环。你知道吗

片段：

a=int(input())
b=list(map(int,input().split()))

maximum = 0
sum = 0
for i in range(0,a):
    if sum < 0:
        sum = 0
    sum += b[i]
    maximum = max(maximum,sum)
print(maximum) 

Answer 2

@vivekè23解决方案更快，但我也会给出我的方法。这将减少迭代次数：

a=int(input())
b=list(map(int,input().split()))
print(max(sum(b[start:end]) for start in range(a) for end in range(0, a + 1) if start < end))

Answer 3

你的问题是你正在做许多迭代的长度列表。相反，你需要想一个更好的方法。一种可能的解决方案可以是递归的，即检查从1到输入的长度，找到最大的总长度，然后递归地调用函数，传递除第一个输入以外的其余输入。这将再次执行相同的检查，直到没有更多的输入需要检查。你知道吗

这并不像@vivekè23的答案那么快，但会给你另一个洞察来解决这样的问题。你知道吗

def max_value(input_list, maximum=float('-inf')):
    input_len = len(input_list)
    if input_len:
        for i in range(1, input_len + 1):
            this_total = sum(input_list[:i])
            if this_total > maximum:
                maximum = this_total
        return max_value(input_list[1:], maximum)
    else:
        return maximum if maximum > 0 else 0


test_inputs = [
    '2 -4 4 3 -2 -1 7 -4 3',
    '63 78 111 43 104 -89 35 57 -55 84 111 91 -18 50 42 100 -67 84 70 63',
    '-5 -6 -8 -7 -9'
]

from timeit import default_timer as timer
for test_input in test_inputs:
    start = timer()
    print(max_value([int(num) for num in test_input.split()]))
    end = timer()
    print('func time taken', end - start)

输出

11
func time taken 0.0009307380000000143
957
func time taken 0.0003775810000000157
0
func time taken 4.153400000000973e-05