如何优化我的maxsum代码并提高时间复杂度？

huangapple
go评论119阅读模式
英文:

How to optimize my maxsum code and improve time complexity?

问题

我在解决HackerRank问题（最大子数组和）。

最大子数组和问题

给定一个整数数组a和一个整数m，确定其任意子数组的和的最大值对m取模。

如何优化我的maxsum代码并提高时间复杂度？

我的代码运行正常，但应该针对更大的集合进行优化。

  1. b=[]
  2. def maximumSum(a, m):
  3.     for i in range(len(a)):
  4.         for j in range(len(a)):
  5.             if j>=i:
  6.                 subarray = a[i:j+1]
  7.                 b.append(subarray)
  9.     return max([sum(i)%m for i in b])

有什么想法？

英文:

I am working on HackerRank problem(maximum-subarray-sum).

maximum subarray sum problem

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.

如何优化我的maxsum代码并提高时间复杂度？

My code works fine, but should be optimized for larger sets.

  1. b=[]
  2. def maximumSum(a, m):
  3.     for i in range(len(a)):
  4.         for j in range(len(a)):
  5.             if j>=i:
  6.                 subarray = a[i:j+1]
  7.                 b.append(subarray)
  9.     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:

  1. array length: 100
  2.   0.64 ± 0.01 ms  Kelly
  3.   1.71 ± 0.00 ms  prhmma
  4.   4.55 ± 0.06 ms  original
  6. array length: 500
  7.  15.63 ± 0.02 ms  Kelly
  8.  45.19 ± 0.20 ms  prhmma
  9. 341.87 ± 1.06 ms  original
  11. array length: 1000
  12.  62.12 ± 0.27 ms  Kelly
  13. 180.37 ± 0.23 ms  prhmma

Code ([Try it online!](https://tio.run/##jVRLbtswEN3rFASKwGSsGrLdFK0AZdNll12qgkFZVExXpASSam0EOVSv0Iu5w48sKUGCaGXO9817M@7O5tDK7ZdOXS4Vq9F31jRnTGMkSBoh@CjKEM3Twj1KeCTu158DbxiiPsZ@@uqyX90qdEJcTiOGKKzREp0IukFi5uM1uO9ROc8Y2uqrla66tsMJcQbFTK8kKqMosvBbxR@4pM10gjLLPXoLiltQisoHhhsmMSUknYE@vuEPII/3GX@JUfclVYqeHV08PS7Xxcs5VrTrmKzwEDybQdATznUvMCc3YgRbFiQM16mDEHQ6WqdYzU87SIK2eVKgW@RROy8UDC4vzL5Xiklztb2LlHkSnj6XdtJiLuSICFyQMIl/td@YM208orfEhFc8b0Ci18TjgG4To9fLv9FikpEfC/Tx2VBLoN/OHJqP6vkho7qXe7vnwy7G/qjioB8EqFYgwwXjBnHRtcqEl/doQw3XhkOR4BWMyhjsFfsdBRNMWbXQ7QP61gLDeyOZ1pElYTeSsJ3csE9Y7Q8t3zONfcA6ub39SmL0K9sk4aAsG87sXuzUQW0wuaFgw/z2heXj0uB68XgNelqQq8a1heGz1mkx8q6Y7htXcVLKgdSa2cGCPwu97Yg/OsYqdwKGaYOBC1f4egQWx@Kn9PcHkj@YQ7qIkfTFLbdWj8c6RXnxDNyTC7GlLe0a15MVMTYrN3BUa7Z1ecbmaeCfVdiVzeuC5OldUUzmc@sAtFjVsAGUn1eb@gn9@4senYTO9snZhEaL8Swmym3uJjjeIZ8ceZwL@FKO@QlYJfzy4YaKsqLpIAzw14uSqWxN5hlh7uG/zJBoLnrgxzUDbOycOWonA3nFBsJBzdVuJ6lgux3UchKvk2QQ2RvunhsgYrDYBSOXy38 "Python 3.8 (pre-release) – Try It Online")):

  1. def Kelly(a, m):
  2.     a = a[:]
  3.     b = 0
  4.     while a:
  5.         s = 0
  6.         for x in a:
  7.             s = (s + x) % m
  8.             if s > b:
  9.                 b = s
  10.         a.pop(0)
  11.     return b
  14. def original(a, m):
  15.     b=[]
  16.     for i in range(len(a)):
  17.         for j in range(len(a)):
  18.             if j >= i:
  19.                 subarray = a[i:j+1]
  20.                 b.append(subarray)
  21.     return max([sum(i)%m for i in b])
  24. def prhmma(a, m):
  25.     prefix_sum = [0] * len(a)
  26.     max_sum = 0
  27.     current_sum = 0
  29.     for i in range(len(a)):
  30.         current_sum = (current_sum + a[i]) % m
  31.         prefix_sum[i] = current_sum
  33.     for i in range(len(prefix_sum)):
  34.         max_sum = max(max_sum, prefix_sum[i])
  36.         for j in range(i + 2, len(prefix_sum)):
  37.             max_sum = max(max_sum, (prefix_sum[j] - prefix_sum[i] + m) % m)
  39.     return max_sum
  42. funcs = original, Kelly, prhmma
  44. from timeit import timeit
  45. from statistics import mean, stdev
  46. import random
  48. # Correctness
  49. for _ in range(3):
  50.     a = random.choices(range(10**9), k=200)
  51.     m = 10**9
  52.     expect = funcs[0](a, m)
  53.     print(f'{expect = }')
  54.     for f in funcs[1:]:
  55.         result = f(a, m)
  56.         assert result == expect
  58. # Speed
  59. def test(n, funcs):
  60.     print('\narray length:', n)
  61.     times = {f: [] for f in funcs}
  62.     def stats(f):
  63.         ts = [t * 1e3 for t in sorted(times[f])[:5]]
  64.         return f'{mean(ts):6.2f} ± {stdev(ts):4.2f} ms ';
  66.     for _ in range(25):
  67.         a = random.choices(range(10**9), k=n)
  68.         m = 10**9
  69.         for f in funcs:
  70.             t = timeit(lambda: f(a, m), number=1)
  71.             times[f].append(t)
  73.     for f in sorted(funcs, key=stats):
  74.         print(stats(f), f.__name__)
  76. test(100, funcs)
  77. test(500, funcs)
  78. 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:

  1. array length: 100
  2. 0.64 ± 0.01 ms  Kelly
  3. 1.71 ± 0.00 ms  prhmma
  4. 4.55 ± 0.06 ms  original
  5. array length: 500
  6. 15.63 ± 0.02 ms  Kelly
  7. 45.19 ± 0.20 ms  prhmma
  8. 341.87 ± 1.06 ms  original
  9. array length: 1000
  10. 62.12 ± 0.27 ms  Kelly
  11. 180.37 ± 0.23 ms  prhmma

Code ([Try it online!](https://tio.run/##jVRLbtswEN3rFASKwGSsGrLdFK0AZdNll12qgkFZVExXpASSam0EOVSv0Iu5w48sKUGCaGXO9817M@7O5tDK7ZdOXS4Vq9F31jRnTGMkSBoh@CjKEM3Twj1KeCTu158DbxiiPsZ@@uqyX90qdEJcTiOGKKzREp0IukFi5uM1uO9ROc8Y2uqrla66tsMJcQbFTK8kKqMosvBbxR@4pM10gjLLPXoLiltQisoHhhsmMSUknYE@vuEPII/3GX@JUfclVYqeHV08PS7Xxcs5VrTrmKzwEDybQdATznUvMCc3YgRbFiQM16mDEHQ6WqdYzU87SIK2eVKgW@RROy8UDC4vzL5Xiklztb2LlHkSnj6XdtJiLuSICFyQMIl/td@YM208orfEhFc8b0Ci18TjgG4To9fLv9FikpEfC/Tx2VBLoN/OHJqP6vkho7qXe7vnwy7G/qjioB8EqFYgwwXjBnHRtcqEl/doQw3XhkOR4BWMyhjsFfsdBRNMWbXQ7QP61gLDeyOZ1pElYTeSsJ3csE9Y7Q8t3zONfcA6ub39SmL0K9sk4aAsG87sXuzUQW0wuaFgw/z2heXj0uB68XgNelqQq8a1heGz1mkx8q6Y7htXcVLKgdSa2cGCPwu97Yg/OsYqdwKGaYOBC1f4egQWx@Kn9PcHkj@YQ7qIkfTFLbdWj8c6RXnxDNyTC7GlLe0a15MVMTYrN3BUa7Z1ecbmaeCfVdiVzeuC5OldUUzmc@sAtFjVsAGUn1eb@gn9@4senYTO9snZhEaL8Swmym3uJjjeIZ8ceZwL@FKO@QlYJfzy4YaKsqLpIAzw14uSqWxN5hlh7uG/zJBoLnrgxzUDbOycOWonA3nFBsJBzdVuJ6lgux3UchKvk2QQ2RvunhsgYrDYBSOXy38 "Python 3.8 (pre-release) – Try It Online")):

  1. def Kelly(a, m):
  2. a = a[:]
  3. b = 0
  4. while a:
  5. s = 0
  6. for x in a:
  7. s = (s + x) % m
  8. if s > b:
  9. b = s
  10. a.pop(0)
  11. return b
  12. def original(a, m):
  13. b=[]
  14. for i in range(len(a)):
  15. for j in range(len(a)):
  16. if j>=i:
  17. subarray = a[i:j+1]
  18. b.append(subarray)
  19. return max([sum(i)%m for i in b])
  20. def prhmma(a, m):
  21. prefix_sum = [0] * len(a)
  22. max_sum = 0
  23. current_sum = 0
  24. for i in range(len(a)):
  25. current_sum = (current_sum + a[i]) % m
  26. prefix_sum[i] = current_sum
  27. for i in range(len(prefix_sum)):
  28. max_sum = max(max_sum, prefix_sum[i])
  29. for j in range(i + 2, len(prefix_sum)):
  30. max_sum = max(max_sum, (prefix_sum[j] - prefix_sum[i] + m) % m)
  31. return max_sum
  32. funcs = original, Kelly, prhmma
  33. from timeit import timeit
  34. from statistics import mean, stdev
  35. import random
  36. # Correctness
  37. for _ in range(3):
  38. a = random.choices(range(10**9), k=200)
  39. m = 10**9
  40. expect = funcs[0](a, m)
  41. print(f'{expect = }')
  42. for f in funcs[1:]:
  43. result = f(a, m)
  44. assert result == expect
  45. # Speed
  46. def test(n, funcs):
  47. print('\narray length:', n)
  48. times = {f: [] for f in funcs}
  49. def stats(f):
  50. ts = [t * 1e3 for t in sorted(times[f])[:5]]
  51. return f'{mean(ts):6.2f} ± {stdev(ts):4.2f} ms '
  52. for _ in range(25):
  53. a = random.choices(range(10**9), k=n)
  54. m = 10**9
  55. for f in funcs:
  56. t = timeit(lambda: f(a, m), number=1)
  57. times[f].append(t)
  58. for f in sorted(funcs, key=stats):
  59. print(stats(f), f.__name__)
  60. test(100, funcs)
  61. test(500, funcs)
  62. 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.

huangapple
  • 本文由 发表于 2023年6月25日 19:47:30
  • 转载请务必保留本文链接：https://go.coder-hub.com/76550238.html
  • algorithm
  • python
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定