Find the minimum number of elements to delete to make the array sorted

Give an array, find the minimum of elements to delete so that the remaining array is sorted.

Method 1: LIS: Onlogn
This is just a cleverly disguised version of the longest increasing sub-sequence problem. If you delete the minimum number of elements to have a sorted sequence, what you're left with is the longest increasing sub-sequence of the original array. Accordingly, you can do the following:
Find the longest increasing subsequence (O(n log n) algorithms exist for this), then
Delete everything not in that subsequence.
http://sudhansu-codezone.blogspot.in/2012/01/longest-increasing-subsequence.html

Method 2:Graph: On2

You can build a DAG based on the elements in the array:
Each element a[n] is a vertex.
For any pair of elements (m,n) where (m < n) and (a[m] <= a[n]) add a directed edge.
Optimization: you can build simple chains for sorted subarrays. For example, if a[m]<=a[m+1)<=a[m+2]<=a[m+3]>a[m+4], you can skip adding the edges (m,m+2) and (m,m+3) for vertex m.
The goal now is to find the longest path in the graph, which has a linear time solution for directed acyclic graphs.