英文:
How to optimize my maxsum code and improve time complexity?
问题
我在解决HackerRank问题（最大子数组和）。
给定一个整数数组a和一个整数m，确定其任意子数组的和的最大值对m取模。
我的代码运行正常，但应该针对更大的集合进行优化。
b=[]
def maximumSum(a, m):
for i in range(len(a)):
for j in range(len(a)):
if j>=i:
subarray = a[i:j+1]
b.append(subarray)
return max([sum(i)%m for i in b])
有什么想法？
英文:
I am working on HackerRank problem(maximum-subarray-sum).
Given an element array of integers a and an integer m determine the maximum value of the sum of any of its subarrays modulo m.
My code works fine, but should be optimized for larger sets.
b=[]
def maximumSum(a, m):
for i in range(len(a)):
for j in range(len(a)):
if j>=i:
subarray = a[i:j+1]
b.append(subarray)
return max([sum(i)%m for i in b])
Any ideas?
答案1
得分: 2
以下是您要翻译的内容：
Quadratic time, just like the accepted answer from prhmma, but simpler and faster. I just accumulate the array suffixes. Benchmark with several array lengths:
array length: 100
0.64 ± 0.01 ms Kelly
1.71 ± 0.00 ms prhmma
4.55 ± 0.06 ms original
array length: 500
15.63 ± 0.02 ms Kelly
45.19 ± 0.20 ms prhmma
341.87 ± 1.06 ms original
array length: 1000
62.12 ± 0.27 ms Kelly
180.37 ± 0.23 ms prhmma
def Kelly(a, m):
a = a[:]
b = 0
while a:
s = 0
for x in a:
s = (s + x) % m
if s > b:
b = s
a.pop(0)
return b
def original(a, m):
b=[]
for i in range(len(a)):
for j in range(len(a)):
if j >= i:
subarray = a[i:j+1]
b.append(subarray)
return max([sum(i)%m for i in b])
def prhmma(a, m):
prefix_sum = [0] * len(a)
max_sum = 0
current_sum = 0
for i in range(len(a)):
current_sum = (current_sum + a[i]) % m
prefix_sum[i] = current_sum
for i in range(len(prefix_sum)):
max_sum = max(max_sum, prefix_sum[i])
for j in range(i + 2, len(prefix_sum)):
max_sum = max(max_sum, (prefix_sum[j] - prefix_sum[i] + m) % m)
return max_sum
funcs = original, Kelly, prhmma
from timeit import timeit
from statistics import mean, stdev
import random
# Correctness
for _ in range(3):
a = random.choices(range(10**9), k=200)
m = 10**9
expect = funcs[0](a, m)
print(f'{expect = }')
for f in funcs[1:]:
result = f(a, m)
assert result == expect
# Speed
def test(n, funcs):
print('\narray length:', n)
times = {f: [] for f in funcs}
def stats(f):
ts = [t * 1e3 for t in sorted(times[f])[:5]]
return f'{mean(ts):6.2f} ± {stdev(ts):4.2f} ms ';
for _ in range(25):
a = random.choices(range(10**9), k=n)
m = 10**9
for f in funcs:
t = timeit(lambda: f(a, m), number=1)
times[f].append(t)
for f in sorted(funcs, key=stats):
print(stats(f), f.__name__)
test(100, funcs)
test(500, funcs)
test(1000, funcs[1:])
英文:
Quadratic time, just like the accepted answer from prhmma, but simpler and faster. I just accumulate the array suffixes. Benchmark with several array lengths:
array length: 100
0.64 ± 0.01 ms Kelly
1.71 ± 0.00 ms prhmma
4.55 ± 0.06 ms original
array length: 500
15.63 ± 0.02 ms Kelly
45.19 ± 0.20 ms prhmma
341.87 ± 1.06 ms original
array length: 1000
62.12 ± 0.27 ms Kelly
180.37 ± 0.23 ms prhmma
def Kelly(a, m):
a = a[:]
b = 0
while a:
s = 0
for x in a:
s = (s + x) % m
if s > b:
b = s
a.pop(0)
return b
def original(a, m):
b=[]
for i in range(len(a)):
for j in range(len(a)):
if j>=i:
subarray = a[i:j+1]
b.append(subarray)
return max([sum(i)%m for i in b])
def prhmma(a, m):
prefix_sum = [0] * len(a)
max_sum = 0
current_sum = 0
for i in range(len(a)):
current_sum = (current_sum + a[i]) % m
prefix_sum[i] = current_sum
for i in range(len(prefix_sum)):
max_sum = max(max_sum, prefix_sum[i])
for j in range(i + 2, len(prefix_sum)):
max_sum = max(max_sum, (prefix_sum[j] - prefix_sum[i] + m) % m)
return max_sum
funcs = original, Kelly, prhmma
from timeit import timeit
from statistics import mean, stdev
import random
# Correctness
for _ in range(3):
a = random.choices(range(10**9), k=200)
m = 10**9
expect = funcs[0](a, m)
print(f'{expect = }')
for f in funcs[1:]:
result = f(a, m)
assert result == expect
# Speed
def test(n, funcs):
print('\narray length:', n)
times = {f: [] for f in funcs}
def stats(f):
ts = [t * 1e3 for t in sorted(times[f])[:5]]
return f'{mean(ts):6.2f} ± {stdev(ts):4.2f} ms '
for _ in range(25):
a = random.choices(range(10**9), k=n)
m = 10**9
for f in funcs:
t = timeit(lambda: f(a, m), number=1)
times[f].append(t)
for f in sorted(funcs, key=stats):
print(stats(f), f.__name__)
test(100, funcs)
test(500, funcs)
test(1000, funcs[1:])
Probably it can be done in sub-quadratic time, but you accepted quadratic time already, and the testing/benchmark code can still be useful when someone comes up with something faster.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论