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?

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.

That's a nice way to put it. Thanks.

This problem is from a hiring challenge.