finding maximum sum of a disjoint sequence of an array

Question

Problem from : https://www.hackerrank.com/contests/epiccode/challenges/white-falcon-and-sequence. Visit link for references.

I have a sequence of integers (-10^6 to 10^6) A. I need to choose two contiguous disjoint subsequences of A, let's say x and y, of the same size, n.

After that you will calculate the sum given by ∑x(i)y(n−i+1) (1-indexed)

And I have to choose x and y such that sum is maximised.

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

Now, the approach that I was thinking of for this is something in lines of O(n^2) which is as follows:

1. Initialise two variables l = 0 and r = N-1. Here, N is the size of the array.
2. Now, for l=0, I will calculate the sum while (l<r) which basically refers to the subsequences that will start from the 0th position in the array. Then, I will increment l and decrement r in order to come up with subsequences that start from the above position + 1 and on the right hand side, start from right-1.

Is there any better approach that I can use? Anything more efficient? I thought of sorting but we cannot sort numbers since that will change the order of the numbers.

Answer 1

To answer the question we first define S(i, j) to be the max sum of multlying the two sub-sequence items, for sub-array A[i...j] when the sub-sequence x starts at position i, and sub-sequence y ends on position j.

For example, if A=[1 7 4 0 9 4 0 1 8 8 2 4], then S(1, 2)=1*7=7 and S(2, 5)=7*9+4*0=63.

The recursive rule to compute S is: S(i, j)=max(0, S(i+1, j-1)+A[i]*A[j]), and the end condition is S(i, j)=0 iff i>=j.

The requested final answer is simply the maximum value of S(i, j) for all combinations of i=1..N, j=1..N, since one of the S(i ,j) values will correspond to the max x,y sub-sequences, and thus will be equal the maximum value for the whole array. The complexity of computing all such S(i, j) values is O(N^2) using dynamic programming, since in the course of computing S(i, j) we will also compute the values of up to N other S(i', j') values, but ultimately each combination will be computed only once.

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