代码之家 › 专栏 › 技术社区 › Kang MinSon

查找以最大和的相同数字开始和结束的子序列

performance python-2.7 algorithm python

-1

Kang MinSon · 技术社区 · 7 年前

我必须制作一个程序,以数字列表作为输入,并返回子序列的和,该子序列以具有最大和的相同数字开始和结束(包括和中子序列开头和结尾的相等数字)。它还必须返回子序列的开始和结束位置,即索引+1。问题是,我当前的代码只有在列表长度不太长的情况下才能顺利运行。当列表长度扩展到5000时,程序不会给出答案。

输入如下:

6
3 2 4 3 5 6

第一行是列表的长度。第二行是列表本身,列表项之间用空格分隔。输出将为 12, 1, 4 ,因为可以看到有1对相等的数字(3):第一个和第四个元素,所以它们之间的元素之和是3+2+4+3=12,它们的位置是第一和第四。

这是我的密码。

length = int(input())
mass = raw_input().split()
for i in range(length):
    mass[i]=int(mass[i])
value=-10000000000

b = 1
e = 1
for i in range(len(mass)):
    if mass[i:].count(mass[i])!=1:
      for j in range(i,len(mass)):
        if mass[j]==mass[i]:
            f = mass[i:j+1]
            if sum(f)>value:
                value = sum(f)
                b = i+1
                e = j+1
    else:
        if mass[i]>value:
            value = mass[i]
            b = i+1
            e = i+1
print value
print b,e

1 回复 | 直到 7 年前

PM 2Ring 7 年前

这应该比您当前的方法更快。

而不是搜索 mass 寻找匹配的数字对,我们将每个数字配对 大量 并对这些对进行排序。然后我们可以使用 groupby 找到数量相等的组。如果有两个以上的相同数字,我们使用第一个和最后一个,因为它们之间的总和最大。

from operator import itemgetter
from itertools import groupby

raw = '3 5 6 3 5 4'
mass = [int(u) for u in raw.split()]

result = []
a = sorted((u, i) for i, u in enumerate(mass))
for _, g in groupby(a, itemgetter(0)):
    g = list(g)
    if len(g) > 1:
        u, v = g[0][1], g[-1][1]
        result.append((sum(mass[u:v+1]), u+1, v+1))
print(max(result))

输出

(19, 2, 5)

请注意,此代码将不如果列表包含负数,则必须给出列表中相等元素之间的最大和。如果没有一组等数的成员超过两个,那么它仍然可以正确处理负数。如果不是这样,我们需要使用一种较慢的算法来测试一组相等数字中的每一对。

这里有一个更有效的版本。而不是使用 sum 函数我们构建一个列表,其中包含整个列表的累积和。这对小列表没有多大影响,但很列表大小较大时速度更快。例如,对于10000个元素的列表,这种方法大约快10倍。为了测试它,我创建了一个随机正整数数组。

from operator import itemgetter
from itertools import groupby
from random import seed, randrange

seed(42)

def maxsum(seq):
    total = 0
    sums = [0]
    for u in seq:
        total += u
        sums.append(total)
    result = []
    a = sorted((u, i) for i, u in enumerate(seq))
    for _, g in groupby(a, itemgetter(0)):
        g = list(g)
        if len(g) > 1:
            u, v = g[0][1], g[-1][1]
            result.append((sums[v+1] - sums[u], u+1, v+1))
    return max(result)

num = 25000
hi = num // 2
mass = [randrange(1, hi) for _ in range(num)]
print(maxsum(mass))

输出

(155821402, 21, 24831)

如果您使用的是Python的最新版本,那么可以使用 itertools.accumulate 建立累计总和列表。这大约快了10%。

from itertools import accumulate

def maxsum(seq):
    sums = [0] + list(accumulate(seq))
    result = []
    a = sorted((u, i) for i, u in enumerate(seq))
    for _, g in groupby(a, itemgetter(0)):
        g = list(g)
        if len(g) > 1:
            u, v = g[0][1], g[-1][1]
            result.append((sums[v+1] - sums[u], u+1, v+1))
    return max(result)

这是一个更快的版本,源于Stefan Pochmann的代码,它使用dict,而不是排序& 子句 . 谢谢Stefan!

def maxsum(seq):
    total = 0
    sums = [0]
    for u in seq:
        total += u
        sums.append(total)
    where = {}
    for i, x in enumerate(seq, 1):
        where.setdefault(x, [i, i])[1] = i
    return max((sums[j] - sums[i - 1], i, j)
        for i, j in where.values())

如果列表不包含重复项(因此没有被重复项绑定的子序列),则返回列表中的最大项。

这里还有两种变体。这些可以正确处理负面项目,如果没有重复的项目,则返回 None . 在Python 3中,可以通过传递 default=None 到 max ,但该选项在Python 2中不可用,因此我捕获 ValueError 尝试查找时引发的异常 最大值 一个空的iterable。

第一版, maxsum_combo ,使用 itertools.combinations 生成一组相等数字的所有组合,并从中找到最大和的组合。第二个版本, maxsum_kadane 使用的变体 Kadane's algorithm 查找组中的最大子序列。

如果原始序列中没有太多重复项,因此平均组大小很小, maxsum\u组合 通常速度更快。但如果群体较大 maxsum\u kadane 是很快于 maxsum\u组合 . 下面的代码在15000个项目的随机序列上测试这些函数,首先测试具有少量重复项的序列(因此平均组大小较小),然后测试具有大量重复项的序列。它验证两个版本是否给出相同的结果,然后执行 timeit 测验。

from __future__ import print_function
from itertools import groupby, combinations
from random import seed, randrange
from timeit import Timer

seed(42)

def maxsum_combo(seq):
    total = 0
    sums = [0]
    for u in seq:
        total += u
        sums.append(total)
    where = {}
    for i, x in enumerate(seq, 1):
        where.setdefault(x, []).append(i)
    try:
        return max((sums[j] - sums[i - 1], i, j)
            for v in where.values() for i, j in combinations(v, 2))
    except ValueError:
        return None

def maxsum_kadane(seq):
    total = 0
    sums = [0]
    for u in seq:
        total += u
        sums.append(total)
    where = {}
    for i, x in enumerate(seq, 1):
        where.setdefault(x, []).append(i)
    try:
        return max(max_sublist([(sums[j] - sums[i-1], i, j)
            for i, j in zip(v, v[1:])], k) 
                for k, v in where.items() if len(v) > 1)
    except ValueError:
        return None

# Kadane's Algorithm to find maximum sublist
# From https://en.wikipedia.org/wiki/Maximum_subarray_problem
def max_sublist(seq, k):
    max_ending_here = max_so_far = seq[0]
    for x in seq[1:]:
        y = max_ending_here[0] + x[0] - k, max_ending_here[1], x[2]
        max_ending_here = max(x, y)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

def test(num, hi, loops):
    print('\nnum = {0}, hi = {1}, loops = {2}'.format(num, hi, loops))
    print('Verifying...')
    for k in range(5):
        mass = [randrange(-hi // 2, hi) for _ in range(num)]
        a = maxsum_combo(mass)
        b = maxsum_kadane(mass)
        print(a, b, a==b)

    print('\nTiming...')
    for func in maxsum_combo, maxsum_kadane:
        t = Timer(lambda: func(mass))
        result = sorted(t.repeat(3, loops))
        result = ', '.join([format(u, '.5f') for u in result])
        print('{0:14} : {1}'.format(func.__name__, result))

loops = 20
num = 15000
hi = num // 4
test(num, hi, loops)

loops = 10
hi = num // 100
test(num, hi, loops)

输出

num = 15000, hi = 3750, loops = 20
Verifying...
(13983131, 44, 14940) (13983131, 44, 14940) True
(13928837, 27, 14985) (13928837, 27, 14985) True
(14057416, 40, 14995) (14057416, 40, 14995) True
(13997395, 65, 14996) (13997395, 65, 14996) True
(14050007, 12, 14972) (14050007, 12, 14972) True

Timing...
maxsum_combo   : 1.72903, 1.73780, 1.81138
maxsum_kadane  : 2.17738, 2.22108, 2.22394

num = 15000, hi = 150, loops = 10
Verifying...
(553789, 21, 14996) (553789, 21, 14996) True
(550174, 1, 14992) (550174, 1, 14992) True
(551017, 13, 14991) (551017, 13, 14991) True
(554317, 2, 14986) (554317, 2, 14986) True
(558663, 15, 14988) (558663, 15, 14988) True

Timing...
maxsum_combo   : 7.29226, 7.34213, 7.36688
maxsum_kadane  : 1.07532, 1.07695, 1.10525

这段代码同时在Python 2和Python 3上运行。上述结果是在一台旧的32位2GHz机器上生成的,该机器在Linux的Debian派生版本上运行Python 2.6.6。Python 3.6.0的速度类似。

如果要包括由单个非重复数字组成的组,并且还希望包括是在作为长度为1的“子序列”的组中,可以使用以下版本:

def maxsum_kadane(seq):
    if not seq:
        return None
    total = 0
    sums = [0]
    for u in seq:
        total += u
        sums.append(total)
    where = {}
    for i, x in enumerate(seq, 1):
        where.setdefault(x, []).append(i)
    # Find the maximum of the single items
    m_single = max((k, v[0], v[0]) for k, v in where.items())
    # Find the maximum of the subsequences
    try:
        m_subseq = max(max_sublist([(sums[j] - sums[i-1], i, j)
                for i, j in zip(v, v[1:])], k) 
                    for k, v in where.items() if len(v) > 1)
        return max(m_single, m_subseq)
    except ValueError:
        # No subsequences
        return m_single

我没有对它进行过广泛的测试,但它应该工作。;)