arrays - 找到数组的不相交序列的最大总和

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 开始.

我可以使用更好的方法吗？还有更高效的吗？我想到了排序，但我们不能对数字进行排序，因为这会改变数字的顺序。

Answer 1

为了回答这个问题，我们首先定义 S(i, j) 为两个子序列项相乘的最大和，对于子数组 A[i...j]，当子序列 x 开始于位置 i，子序列 y 结束于位置 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