Statement: For each i, length of current set is equal to the length of the largest increasing subsequence.
Proof: Lets use the method of induction:
Base case : Trivially true.
Induction hypothesis: Suppose we have processed i-1 elements and the length of the set is LIS[i-1], i.e the length of the LIS possible with first i-1 elements.
Induction step: Inserting an element array[i] in the set will result in two cases.
A[i] >= set.last() : In this case A[i] will be the last element in the set and hence the LIS[i] = LIS[i-1]+1.
A[i] < set.last() : In this case we insert A[i] into the set and knock off element just greater than A[i] in the sorted order. LIS[i] = LIS[i-1] + 1(adding A[i]) - 1 (removing one elem > A[i]). Which is true. Hence proved.
To explain the big picture. Inserting A[i] into the set will either add to the LIS[i-1] or will create a LIS of its own, which will be the elements from 0th position to the position of the ith element.