how to solve this

Правка en1, от nagato_uzumaki, 2020-10-27 12:17:31

problem:-

we are given an array of length n(n<=3000) having integers( from -10^6 to 10^6), we need to chose two disjoint (i.e. they should not overlap) sub-arrays of same length from the array so that the product of two sub-arrays is maximum possible , we just need to find here the maximum product that can be attained..

product of two sub-array 'a' and 'b' of length 'k' is defined as follows:- sum of all (a[i]*b[k-i-1])...

for eg:--

arr = {1, 9, 2, 3, 0, 6, 7, 8}

then here maximum product is 104 by picking by sub-arrays of length 3 :- {9, 2, 3} and {6, 7, 8} product = 9*8 + 2*7 + 3*6 = 104, which is maximum possible here...

I think this is a DP problem(maybe i am wrong) but am getting confused in picking states and transition here.. so please help ...

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский nagato_uzumaki 2020-10-27 12:17:31 803 Initial revision (published)