nagato_uzumaki's blog

how to solve this
By nagato_uzumaki, history, 4 years ago, In English

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

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    thanks for help, can u a bit elaborate what u mean by overlapping indices

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      Maybe this will help 1 9 2 3 0 6 7 8

      taking 0(index 4) as pivot and rotating(indices 0 to 3) 180 degrees->

      0 (6,3) (7,2) (8,9) 1

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        you 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)

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it +5 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            ok, I will try to implement this, thanks for the idea though..

            → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it
DP solution
→ Reply