vaibhavmisra's blog

By vaibhavmisra, history, 11 months ago, In English

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?

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

11 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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.

11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem is from a hiring challenge.