Блог пользователя nagato_uzumaki

Автор nagato_uzumaki, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        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)

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

          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.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
DP solution