在一个数组中找到不相交子序列的最大和

Question

问题来源： https://www.hackerrank.com/contests/epiccode/challenges/white-falcon-and-sequence。 请点击链接查看参考资料。

我有一个整数序列(-10^6到10^6) A。我需要选择两个连续的不相交的A子序列，分别为x和y，它们的长度都是n。

然后你需要计算由∑x(i)y(n−i+1)（从1开始编号）给出的总和。

我必须选择x和y使得总和最大化。

Eg: 
Input: 
12
1 7 4 0 9 4 0 1 8 8 2 4 

Output: 120

Where x = {4,0,9,4}
y = {8,8,2,4}

∑x(i)y(n−i+1)=4×4+0×2+9×8+4×8=120

现在，我想到的方法大致是O(n^2)，具体如下：

1. 初始化两个变量 l = 0 和 r = N-1。这里，N 是数组的大小。
2. 现在，对于 l=0，我将计算当 (l<r) 时的总和，这基本上是指从数组中的第0个位置开始的子序列。然后，我将增加 l 并减少 r，以便得出从上述位置+1开始并且在右侧从 right-1 开始的子序列。

有没有更好的方法？任何更有效的方法？我想过排序，但我们不能排序数字，因为那会改变数字的顺序。

- John Lui

---

这些数字总是非负数吗？ - Peter de Rivaz

不，这些数字也可以是负数。 - John Lui

我不明白你的O(n^2)方法如何正确。如果x从位置i开始，你怎么能确定存在一个最优的y从n-i-1开始呢？ - Niklas B.

比赛早已结束，如果我有疑问，在这里发帖也没有任何伤害。毕竟，这是一个开放的讨论论坛。 - John Lui

@JohnLui，你能提供原始问题陈述的链接吗？它可能包含比你在问题中写的更多信息。我很难相信有一个O(n^2)的解决方案（这是小o，不是大O）。 - Niklas B.

Answer 1

为了回答这个问题，我们首先定义S(i, j)为当子序列x从位置i开始，子序列y在位置j结束时，子数组A[i...j]的两个子序列项的最大乘积之和。

例如，如果A=[1 7 4 0 9 4 0 1 8 8 2 4]，那么S(1, 2)=1*7=7，S(2, 5)=7*9+4*0=63。

计算S的递归规则是：S(i, j)=max(0, S(i+1, j-1)+A[i]*A[j])，终止条件是S(i, j)=0，如果i>=j。

所请求的最终答案只是对于所有i=1..N，j=1..N的组合，S(i, j)的最大值，因为其中一个S(i,j)值将对应于最大的x,y子序列，因此将等于整个数组的最大值。使用动态规划计算所有这些S(i, j)值的复杂度为O(N^2)，因为在计算S(i, j)的过程中，我们还会计算多达N个其他S(i', j')值的值，但最终每个组合只会被计算一次。

def max_sum(l):
  def _max_sub_sum(i, j):
    if m[i][j]==None:
      v=0
      if i<j:
        v=max(0, _max_sub_sum(i+1, j-1)+l[i]*l[j])
      m[i][j]=v
    return m[i][j]

  n=len(l)
  m=[[None for i in range(n)] for j in range(n)]
  v=0
  for i in range(n):
    for j in range(i, n):
      v=max(v, _max_sub_sum(i, j))
  return v

- gen-y-s

---

为了澄清S(i,j)的定义，这里有一个带有负数的例子：A[1,2,3,-4,5,6]。S(3,4)=max(0, 3*(-4))=0，S(2,5)=max(0,2*5+S(3,4))=10。也就是说，S(2,5)等于10，因为它使用每个元素自身作为子序列x=A[2..2]=[2]和y=A[5..5]=[5]，而不是更多（例如，x=A[2..3] y=A[4..5]），因为那会得到更低的总和。主要观点是用于计算S(i,j)的子序列x和y始终是以i开始且以j结束的。只有它们的长度不同，使得S(i,j)最大化。 - gen-y-s

递归关系应为S[i,j]=max(A[i]*A[j],S[i+1,j-1]+A[i]*A[j])，如果i+2<j，则S[i,j]，对于所有的1<=i<j<=N（从1开始计数），如果i+1==j或i+2==j，则S[i,j]=A[i]*A[j]。 - Jason L

你可以像你所做的那样呈现递归表达式，但这与我指定的没有区别。例如，在我的公式中，当j=i+2时，S(i,j)=max(0, S(i+1, j-1)+A[i]*A[j])=max(0, S(i+1, i+1)+A[i]*A[j])=max(0, A[i]*A[j])，这与你的定义相同（除了S(i, j)永远不可能为负）。 - gen-y-s

Answer 2

警告：

此方法假定数字为非负数，因此该解决方案不适用于帖子的实际问题，现在已经澄清允许使用负输入值。

技巧1

假设数字始终为非负数，则在它们相遇的位置上尽可能使序列变宽是最好的选择。

技巧2

我们可以通过对i的所有值求和将总和转换为标准卷积。这会产生两倍于所需结果的值（因为我们得到了x与y的乘积以及y与x的乘积），但我们可以在最后除以2来获得原始答案。

技巧3

您现在正在尝试找到信号自身卷积的最大值。有一种标准方法可以使用快速傅里叶变换来完成此操作。一些库将内置此功能，例如Scipy中有fftconvolve。

Python代码

请注意，不允许重复使用中心值（例如对于序列1,3,2，我们无法将x设为1,3，y设为3,1），因此需要检查卷积输出的其他值。

现在，我们可以通过Python计算答案：

import scipy.signal
A = [1, 7, 4, 0, 9, 4, 0, 1, 8, 8, 2, 4]
print max(scipy.signal.fftconvolve(A,A)[1::2]) / 2

- Peter de Rivaz