algorithm - 素数长度的所有连续子数组的最大总和

Question

我最近在面试中被问到这个问题，

Given an array of non-negative integers find the maximum cumulative sum that could be obtained such that the length of all the participating subarray is a prime number. I tried to come up with a solution for this using Dynamic Programming but unfortunately could not.

例如:如果数组是 [9,8,7,6,5,4,3,1,2,2]，它应该返回 46(子数组 [ 9,8,7,6,5,4,3] 长度为 7 和 [2,2] 长度为 2)。您不能组合 [9,8,7,6,5,4,3] 和 [1,2,2]，因为它会导致长度为 10 的非素数的连续子数组(幂等性)。

谁能解释一下如何使用DP解决此类问题？谢谢。

Answer 1

你可以做什么:

• 取列表的长度并返回，直到找到素数
• 获取元素的窗口并对它们求和
• 检查它是否是最大总和，如果是，存储它
• 转到下一个窗口

之所以可行，是因为所有整数都是正数的限制，否则它不会起作用。

基本上是这样的(非常粗略，在伪python中，显然没有测试过):

input_list = (8, 1, 3, 4, 5, 2)
list_size = len(input_list)

while (list_size):
    if (is_prime(list_size)):
        window_size = list_size
        break
    list_size--

max_sum = -1
for i in xrange(0, list_size - window_size):
    current_sum = sum(input_list[i:i+window_size])
    if (max_sum < current_sum):
        max_sum = current_sum

print max_sum