P S*_*nki 6 python arrays algorithm dynamic-programming
我试图总结问题陈述如下：
给定n,k和一个数组（列表）arr，其中n = len(arr)和k是integerin set (1, n) inclusive。
对于数组（或列表）myList，不公平总和被定义为sum中所有可能对（每个组合有 2 个元素）之间的绝对差的myList。
解释一下：如果mylist = [1, 2, 5, 5, 6]那么最小不公平总和或 MUS。请注意，元素index在列表中被认为是唯一的，而不是它们的值
MUS = |1-2| + |1-5| + |1-5| + |1-6| + |2-5| + |2-5| + |2-6| + |5-5| + |5-6| + |5-6|
如果您确实需要查看问题陈述，则在此处
我的目标
给定n, k, arr（如上所述），Minimum Unfairness Sum从所有可能的子数组不公平总和中找出每个可能的约束len(sub array) = k[这是让我们的生活更轻松的一件好事，我相信:)]
我试过的
好吧，这里有很多东西要添加，所以我会尽量简短。
我的第一种方法是我曾经itertools.combinations获得所有可能的组合并statistics.variance检查它的spread of data（是的，我知道我一团糟）。
在您看到下面的代码之前，您是否认为这些方差和不公平总和是完全相关的（我知道它们是强相关的），即 的子数组minimum variance必须是MUS??
你只需要检查LetMeDoIt(n, k, arr)功能。如果您需要MCVE，请检查下面的第二个代码片段。
from itertools import combinations as cmb
from statistics import variance as varn
def LetMeDoIt(n, k, arr):
v = []
s = []
subs = [list(x) for x in list(cmb(arr, k))] # getting all sub arrays from arr in a list
i = 0
for sub in subs:
if i != 0:
var = varn(sub) # the variance thingy
if float(var) < float(min(v)):
v.remove(v[0])
v.append(var)
s.remove(s[0])
s.append(sub)
else:
pass
elif i == 0:
var = varn(sub)
v.append(var)
s.append(sub)
i = 1
final = []
f = list(cmb(s[0], 2)) # getting list of all pairs (after determining sub array with least MUS)
for r in f:
final.append(abs(r[0]-r[1])) # calculating the MUS in my messy way
return sum(final)
上面的代码可以正常工作，n<30但MemoryError超出了这个范围。在 Python 聊天中，Kevin 建议我尝试generator哪个是memory efficient（它确实是），但是由于生成器也会在我们iterate经过它们时动态生成这些组合，因此对于 n=50, k 应该需要 140 多个小时 (:/) =8 估计。
我在 SO HERE上发布了与问题相同的问题（您可能想看看以正确理解我 - 它有讨论和融合的答案，这将我带到我的第二种方法 - 更好的方法（我应该说融合的方法 xD）） .
第二种方法
from itertools import combinations as cmb
def myvar(arr): # a function to calculate variance
l = len(arr)
m = sum(arr)/l
return sum((i-m)**2 for i in arr)/l
def LetMeDoIt(n, k, arr):
sorted_list = sorted(arr) # i think sorting the array makes it easy to get the sub array with MUS quickly
variance = None
min_variance_sub = None
for i in range(n - k + 1):
sub = sorted_list[i:i+k]
var = myvar(sub)
if variance is None or var<variance:
variance = var
min_variance_sub=sub
final = []
f = list(cmb(min_variance_sub, 2)) # again getting all possible pairs in my messy way
for r in f:
final.append(abs(r[0] - r[1]))
return sum(final)
def MainApp():
n = int(input())
k = int(input())
arr = list(int(input()) for _ in range(n))
result = LetMeDoIt(n, k, arr)
print(result)
if __name__ == '__main__':
MainApp()
此代码适用于n up to 1000（可能更多），但由于time out（5 秒是在线判断的限制 :/ ）而终止10000（最大的测试用例有n=100000）。
======
您将如何处理此问题以在给定的时间限制（5 秒）内处理所有测试用例？（问题列在algorithm&下dynamic programming）
（对于您的参考，您可以查看
编辑 1 ::
对于这个问题的未来观众，我到现在得出的结论是，
这variance并unfairness sum没有perfectly相关的（它们是strongly相关的），这意味着一个批次整数列表中，与列表minimum variance并不总是必须与列表中minimum unfairness sum。如果你想知道为什么，我实际上是作为一个关于数学堆栈交换的单独问题在这里提出的 ，其中一位数学家为我证明了它xD（值得一看，因为这是出乎意料的）
就整个问题而言，您可以阅读下面的 archer & Attersson 的答案（仍在尝试找出一种天真的方法来执行此操作 - 不过现在应该不远了）
感谢您的任何帮助或建议:)
我发现这个问题仍然没有完整的答案。我将写一个正确算法的轨迹，该算法将通过评审。为了尊重 Hackerrank 挑战的目的，我不会编写代码。因为我们有可行的解决方案。
原始数组必须已排序。其复杂度为 O(NlogN)
此时，您可以检查连续的子数组，因为不连续的子数组将导致更差（或相等，但不是更好）的“不公平总和”。archer的回答中也解释了这一点
最后一个检查段落，找到最小的“不公平总和”可以在 O(N) 内完成。您需要计算每个连续 k 长子数组的 US。错误是在 O(k) 内完成的每一步都重新计算，这使得这段代码的复杂性达到了 O(k*N)。正如您发布的社论所示，它可以在 O(1) 中完成，包括数学公式。它需要在步骤 1 之后预先初始化累积数组（在 O(N) 中完成，空间复杂度也是 O(N)）。
它可以工作，但由于 n<=10000 超时而终止。
（来自对弓箭手问题的评论）
为了解释步骤 3，考虑 k = 100。您正在滚动 N 长数组，并且第一次迭代，您必须像往常一样计算子数组从元素 0 到 99 的 US，需要 100 次。下一步需要您计算与前一个仅相差 1 个元素（1 到 100）的子数组。然后是 2 到 101，等等。如果有帮助，请将其想象为一条蛇。删除一个块并添加一个块。不需要执行整个 O(k) 滚动。只需按照社论中的说明进行数学计算，即可在 O(1) 内完成。
因此，由于第一次排序，最终的复杂度将渐近为 O(NlogN)。