Confused101's blog

Maximum Submatrix with distinct elements
By Confused101, history, 8 years ago, In English 
Given a 2D matrix of size nxm (n, m <= 400), Calculate maximum submatrix such that all of its elements are distinct? [maximum submatrix is submatrix whose area is maximum]
P.S.
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

407D - Наибольшая подматрица 3

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    Thankyou! this was the problem I was trying to find. can someone explain how to solve it
    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Suppose you fix two rows of the matrix. Can you come up with a way of calculating the answer for this "slice" in O(m)?

Hint: Incrementing the "right" column will impose some constraints (lower bounds) on the "left" column.

→ Reply