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

Minimum operations to sort an array
Автор vaibhavmisra, история, 3 года назад, По-английски

Operation : Change any array element to arbitrary integer, O(N^2) would give TLE, My approach : ans = Length of array — Length of longest non-decreasing sub-sequence because I want maximum length already sorted, TC : O(NlgN),
Is this approach correct? Any other approaches?

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

»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

I think you're right. Since changing an element can be seen as simply delete it, the problem is actually finding a longest sorted subsequence. Thus it's indeed a LIS problem.

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This problem is from a hiring challenge.

→ Ответить