Problem 1914. GJam 2013 Veterans: Ocean View (Large)

This Challenge is derived from GJam 2013 Veterans Ocean View. This is the Large data set with N<=1000 and Q<N<=1000, with typical 80.

The GJam story goes that as Supreme Ruler you are annoyed by complaints of non-ocean views on a hillside. To resolve the issue a minimum number of homes will be removed to provide a maximum number of ocean view homes. The Elevation of the homes should monotonically increase, no equal values, from element 1 thru the end.

Succinct Challenge statement: Given a vector create the maximum length monotonically increasing vector by removing values. Report the number of values removed.

Input: V , Vector length N<=1000 with values 1 thru 1000.

Output: Q , minimum quantity of removed values to produce a valid vector (typical 80)

Examples: [V] [Q]

[1 4 3 3] [2]  for [1 4] or [1 3]
[1 2 3 4 5] [0]
[4 3 2 1] [3]

Commentary:

1) nchoosek(1000,80) is a little big
2) The Large test suite is N<=1000 with some delete cases >4
3) A Good Algorithm that solves the Large case is usually best to pursue
4) GJam Competition allows one Large submission within 10 minutes of download 
5) This was only solved by one entrant.

Small Suite Challenge

Algorithm Spoiler: A general method is to start at the end and build all unique length valid vectors. It is only necessary to maintain a Min Value and length for the potential solutions. Once all values are checked find the maximum solution length. There are three key steps in this method: 1) If vin(j)> Max of all solutions, start a new solution with length 1. 2) Find solutions that are 1 greater than vin(j). Update minimums of these solutions with vin(j) and increase length values. 3) Find solutions where mins>vin(j). Augment solution set by a single line of [vin(j),max length found +1]. 4) Find maximum length solution. This method solved all 100 large cases in < 2 seconds on Cody.