最佳长度的所有连续的子阵列

最近，我问这个问题在接受采访时的最大总和，最佳长度的所有连续的子阵列

鉴于非负整数数组发现，能够获得这样的长度最大累积总和所有参与子阵列是一个素数。我试图想出一个使用动态规划的解决方案，但不幸的是不能。

例如：如果阵列是[9,8,7,6,5,4,3,1,2,2]它应该返回（子阵列[9,8的总和， 7,6,5,4,3]长度7和[2,2]长度2）。你不能合并[9,8,7,6,5,4,3]和[1,2,2]，因为它会导致长度为10的连续子矩阵（幂等性），它是非素数。

任何人都可以解释如何使用DP解决这些问题？谢谢。

来源

2017-03-02 GeT_RiGhT

为什么不15？ [8,4,3] - 长度是一个素数（3）。你没有说所有的元素都应该是素数。 –

为什么要使用动态编程？这只是首先找到最大素数（从列表长度后退），然后是具体长度的最大子数组，这是一个非常常见的问题。 – ChatterOne

@user它应该包含连续的元素。对不起忘了提到这一点。修复！ –

由于其他人已经解决了非负整数的问题。

但是，如果你有-ve数字，那么这个算法也会起作用。我认为你必须稍微调整Kadane's Algo。

以下是修改后的Kadane Algo的变化。所有标记**的行都是变化的。

Initialize: 
    max_so_far = 0 
    max_ending_here = 0 
    ** MAX_SO_FAR_FOR_PRIMES =0 
    ** SUB_ARRAY_SIZE = 0 

Loop for each element of the array 
    max_ending_here = max_ending_here + a[i] 
    ** SUB_ARRAY_SIZE = SUB_ARRAY_SIZE + 1 // since a[i] included in subarray, increase sub_array_size 
    if(max_ending_here < 0) 
      max_ending_here = 0 
    **   SUB_ARRAY_SIZE = 0 
    if(max_so_far < max_ending_here) 
      max_so_far = max_ending_here 
    ** if(MAX_SO_FAR_FOR_PRIMES < max_ending_here && isPrime(SUB_ARRAY_SIZE)) // comparing when SUB_ARRAY_SIZE is Prime. 
    **  MAX_SO_FAR_FOR_PRIMES = max_ending_here.  

return MAX_SO_FAR_FOR_PRIMES

基本上，需要多一个变量MAX_SO_FAR_FOR_PRIMES，这使的黄金尺寸的子阵列的最大总和子数组为止。

还存储SUB_ARRAY_SIZE，它在循环期间随时存储子数组的大小。

现在只要比较你MAX_SO_FAR_FOR_PRIMES与你的max_ending_here只要SUBARRAY_SIZE是质数。并相应地更新MAX_SO_FAR_FOR_PRIMES1。

来源

2017-03-02 08:24:46

对不起。我错误地提出了这个问题。修复！我仍然可以使用Kadane算法解决它吗？ –

我需要素数长度的所有连续子数组的累计和。更新了问题。请看看它。谢谢 –

你可以做什么：

采取列表的长度并返回，直到找到一个素数
得到元素的窗口，总结他们
检查，如果它的最大总和并且如果是这样，其存储
进入下一个窗口

这工作，因为共同的如果所有整数都是正数，那么它就不会起作用。

基本上是这样的（很粗略，在伪巨蟒，显然未测试）：

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

来源

2017-03-02 08:44:58 ChatterOne

我错误地提出了问题并现在修复了它。你能重新看一下吗？谢谢。 –

用（100,1,1,1,1,100）进行测试。它将返回总和104的单个5元素子阵列，但最大值是203. –

@ n.m。这是因为这个问题明确地说“连续的子阵列”。 – ChatterOne

如何像这样（大约）O(n * n/log n)时间，O(n)空间，DP？

让f(i)代表最大的总和，直至索引i，其中a[i]或者排除在连续子集之外或者是素长度子集的最后一个。然后：

f(i) = sum(a[0]...a[i]) if (i + 1) is prime, otherwise 
    max(
    // a[i] excluded 
    f(i-1), 
    f(i-2), 

    // a[i] is last of a subset 
    sum(a[i - primes[j] + 1]...a[i]) + f(i - primes[j] - 1) 
     for primes[j] <= i 
)

（加间隔可在O(1)时间内完成与O(n)预处理前缀总和。）

来源

2017-03-02 15:39:42

当[i]是子集的最后一位时，能否请您解释重现的含义？或者更好的是，你能解释一下你是如何抵达重现是外行的条件？我不明白它意味着什么。谢谢:) –

@GeT_RiGhT'subset'，我的意思是子阵列。如果一个[i]不是子数组的一部分，我们就不会将其作为总和的一部分，所以在这种情况下，最大和为i的总和将是最大总和（i-1）或（ I-2）。之后，我们处于一个情况，即一个[i]可能是一个长度为2或更长的子数组的最后一个。然后，我们逐一比较这些可能性：如果它的长度为2，我们将它的最大和增加到（i - 2 -1），即f（i-2-1）。如果它是5，我们加上和f（i-5-1）等等。 –

如果a [i]不是子阵列的一部分，我们为什么要考虑max-upto（i-1）或（i-2）？另外什么是f（0）？ –

最佳长度的所有连续的子阵列

回答

相关问题