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 ...
From what I understood,you are just basically rotating array 180 degrees and then calculating sum of products of overlapping indices, so you can calculate all such products by making indices pivot point staring from i=2 to n-1, and then take maximum of these, final time complexity will be, O(n) for rotating* O(n) for calculating product,so O(n^2).
Correct me if I am wrong.
thanks for help, can u a bit elaborate what u mean by overlapping indices
Maybe this will help
1 9 2 3 0 6 7 8taking 0(index 4) as pivot and rotating(indices 0 to 3) 180 degrees->
0 (6,3) (7,2) (8,9) 1you are always excluding pivot in this way , right? so it means that we are not accounting for all those two subarrays who are neighbours? (i,e. end of first — start of second != 1)
Take pivot as all indices as well as between two adjacent indices, I just mentioned it to make you understand about overlapping elements, if you implement this then you have to make some necessary changes which are obvious.
ok, I will try to implement this, thanks for the idea though..
Let $$$dp[i][j]$$$ $$$(i < j)$$$ be the maximum possible answer if $$$i$$$ is the first index in the first chosen sub-array and $$$j$$$ is the last index in the second chosen sub-array. Then if $$$j - i > 2$$$, $$$dp[i][j]$$$ will be $$$a[i] * a[j] + max(0, dp[i + 1][j - 1])$$$, otherwise it will just be $$$a[i] * a[j]$$$. We have to iterate in the increasing order of $$$j - i$$$, that way it is guaranteed that when we compute $$$dp[i][j]$$$, $$$dp[i + 1][j - 1]$$$ is already computed. Finally, the answer will be maximum out of all the $$$dp[i][j]$$$.
Time complexity $$$O(n^2)$$$.
really glad for ur help, thanks..