fake_id_123's blog

By fake_id_123, history, 3 years ago, In English

Given an array which is also an permutation.
How many tuples are there such that

$$$ i < j < k < l$$$ and $$$ a_i < a_k < a_j < a_l $$$

Another variation was

$$$ i < j < k < l < m $$$ and $$$ a_i < a_k < a_j < a_m < a_l $$$

P.S., this was interview question so no constraints were given, what is best complexity can we achieve.

Full text and comments »

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