问题描述
我在从HackerRank遇到 。
此问题开始时定义大小为n的零数组，然后对其进行运算。
因此，假设数组为x = [0, 0, 0, 0, 0, 0] 。
所以这里n = 6 。
现在考虑该操作（在问题中称其为查询） [1, 2, 5] 。
这意味着在数组x ，将5从索引0加到1。因此x现在变成x = [5, 5, 0, 0, 0, 0] 。
并且可能有许多这样的操作（查询）。
最后，我们只需要找到最终数组x的max元素。
所以样本输入是
5 3
1 2 100
2 5 100
3 4 100
因此，我们需要具有大小为5的数组x （初始化为零），并在其上运行3个查询。
如果我们进行查询，我们发现最终数组中的max元素为200。我在这里使用嵌套的for循环完成了代码。
外部for循环遍历查询，内部for循环操纵数组x 。
对于x的数组大小的较小值，我的代码运行良好。
但是，当n = 1000000且查询数量为m = 100000 ，嵌套的for循环将永远运行（它就像一个无限循环）。
我想知道如何使它更快。
以下是嵌套的for循环
# Construct a zero list of length n
worklist = list([0]*n)
# Loop through the queries
for query in queries:
# Since the problem defines the queries vector
# as one based index, we need to modify the
# indices of query
index0, index1 = query[0]-1, query[1]-1
# Now construct the new list with addition
for i in range(index0, index1+1):
worklist[i] = worklist[i] + query[2]
我认为我需要为此修改算法。 欢迎提出建议。
1楼
在此问题的“讨论”页面上，那里有一个O（n）解决方案，这是有关重叠的问题。
基本思路是，您只需要在数组中标记“添加”点和“删除”点，因此最后阶段只需要遍历数组一次并将“当前总和”保留在当前索引中，即可记录最多一个答案。
例如5 3
1 2 100
2 5 100
3 4 100
您的数组将简化为
0、0、0、0、0、0
取第一个输入记录（1 2 100）时：
100、0，-100、0、0、0
这意味着当您进行最终扫描总和摘要时，您的循环将在步骤中计算
索引0，总和100
索引1，总和100
索引2，总和0
索引3，总和0 ...
取第二条输入记录（2 5 100）时：
100、100，-100、0、0，-100
这意味着当您进行最终扫描总和摘要时，您的循环将在步骤中计算
索引0，总和100
索引1，总和200
索引2，总和100
索引3，总和100
索引4，总和100
索引5，总和0
因此最大值发生在索引1
取第二条输入记录（3 4 100）时：
100、100、0、0，-100，-100
这意味着当您进行最终扫描总和摘要时，您的循环将在步骤中计算
索引0，总和100
索引1，总和200
索引2，总和200
索引3，总和200
索引4，总和100
索引5，总和0
因此最大值发生在索引1
2楼
我的回答只讨论你的问题的算法部分，我将简化的I / O，而不是执行它作为一个功能，让在其上测试你的技能的东西。
这个想法是，不存储结果，而是每个位置上的累计增量和，后来，找到累积求和的最大值。
让我们来看看在问题的陈述报告的第一个例子，
10 3
1 5 3
4 8 7
6 9 1
我们先从l ，零列表长度等于n+1 （为什么n+ 1，因为我们需要一点额外的空间来存储增量是什么时候？ b==n ）;
我们希望在存储l只是差异的
n, m = 10, 3
l = [0]*(n+1)
我们重复相同的OPS为3个查询和报告我们的列表的状态l的评论
a, b, k = 1, 5, 3
l[a-1] += k ; l[b] -= k
# [0, 0, 3, 0, 0, -3, 0, 0, 0, 0, 0]
a, b, k = 4, 8, 7
l[a-1] += k ; l[b] -= k
# [0, 0, 3, 7, 0, -3, 0, 0, -7, 0, 0]
a, b, k = 6, 9, 1
l[a-1] += k ; l[b] -= k
# [0, 0, 3, 7, 1, -3, 0, 0, -7, -1, 0]
current_max = 0
current_sum = 0
debug = 1
for num in l[:-1]:
current_sum += num
if debug: print(current_sum)
current_max = max(current_max, current_sum)
print(current_max)
执行上面的代码给了我
3
3
3
10
10
8
8
8
1
0
10
前十个数是总结列表中的元素，与问题的陈述进行比较，最后数字是必需的最大值