列表中两个切片的 Min-Maxing / max-value

Question

我有一个像 [3,10,4,3,9,15,6,13] 这样的列表，我想找到两个不重叠的系列/序列，并通过取最大-最小值给出可获得的最大值。它们必须是连续的，所以你不能从 1 中减去项目 3。但是你可以从 3 中减去索引 1。

所以在我的示例中，您将得到 [3,10] 和 [3,15] 对。你怎么能以编程方式做到这一点。这是我到目前为止得到的。

python:

l = [3,10,4,3,9,15,6,13]
pair1=[max(l), min(l)]
l.remove(max(l))
l.remove(min(l))
pair2=[max(l), min(l)]

这当然不是我想要的，但我不确定如何继续寻找两对。找到一对上面的代码可以正常工作，但不能找到两个，因为您通常会得到重叠的序列。

Answer 1

可能不是那么优雅，但试试这个：

l = [3,10,4,3,9,15,6,13]

# list to store diffs
diff=[]
# calculate diffs
for i in range(0, len(l)-1):
    diff.append(l[i+1]-l[i])

# list to store diff sequences
results=[]

# Findinf the sequences
curr=0;
while curr<=(len(diff)-1):

    # list to store positive differences
    result=[]

    # llop while the difference is positive
    while diff[curr]>0 :

        # if it is a first element
        if len(result) == 0:
            # in 0th place store the diff sum
            result.append(diff[curr])
            # in 1st place store the sequence start index 
            result.append(curr)
            # in 2nd place store the sequence end index
            result.append(curr+1)
        else:
            # summ the sequnce diff
            result[0]+=diff[curr]
            # update sequence end index
            result[2]=curr+1
        # move to next element
        curr+=1
        # if reached end of array, break the loop 
        if curr>(len(diff)-1):
            break
    # if there was a sequence store it             
    if (len(result) > 0):
        results.append(result)
    else:
        # move to next element in case of there was no sequence
        curr+=1

# sort the results by sum in reverse order of the 0th element(sum) and normal order of 1st element(start index)
results.sort(key=lambda x: x[0]*10-x[1], reverse=True)
# print first 2 results
for i in range(0,2):
    print "[%d,%d]" % (l[results[i][1]],l[results[i][2]])

至少对于您的输入，它会打印出想要的结果:)

Answer 2

写这个很有趣：

import itertools as it

l = [3,10,4,3,9,15,6,13]

r=sorted(
    map(lambda x: (x[0:2], x[2:4]),
        sorted(it.imap(
            lambda x: (min(x[0:2]), max(x[0:2]), min(x[2:4]), max(x[2:4])),
            it.imap(lambda x: (l[x[0]], l[x[1]], l[x[2]], l[x[3]]),
                    it.combinations(range(len(l)), 4))),
               key=lambda x: -(x[1]-x[0]+x[3]-x[2])))[0],
    key=lambda x: x[0]-x[1])

print(r)

列表中两个切片的 Min-Maxing / max-value

Min-Maxing / max-value of two slices in a list

python

list

max

min