4

I found algorithm mentioned in The Hitchhiker’s Guide to the Programming Contests (note: this implementation assumes there are no duplicates in the list):

set<int> st;
set<int>::iterator it;
st.clear();

for(i=0; i<n; i++) {

  st.insert(array[i]); it=st.find(array[i]);

  it++; if(it!=st.end()) st.erase(it);
}

cout<<st.size()<<endl;

It's an algorithm to find longest increasing subsequence in O(NlogN). If I try to work it with few test cases, it seems to work. But I still couldn't figure out its correctness logic. Also, it doesn't look so intuitive to me.

Can anyone help me gain insight as to why this algorithm works correctly?

aamir
  • 3,753
  • 4
  • 23
  • 34
  • Hint: Read about `Dynamic programming`, `memoization` and also this http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-21-dp-iii-parenthesization-edit-distance-knapsack/ – noMAD Dec 14 '13 at 20:52
  • Dynamic programming solution is O(n*n) as far as I know. – aamir Dec 14 '13 at 20:53
  • @AamirKhan Dynamic programming is a general problem solving technique, applying it can result in solutions with very different time complexity depending on the problem and how you applied it. The dynamic programming fibonacci is linear time, for example. –  Dec 14 '13 at 20:56
  • That's the beauty of this algorithm. It will give you the correct length of LIS but the elements in the set needn't be the one constituting that! In this case algo will return 5 as answer though set would have elements {1,2,4,7,9} – aamir Dec 14 '13 at 20:57
  • Longest chain length equals size of smallest cover by antichains (Dilworth's thoerem). You can show that, for this poset, finding the antichain cover greedily produces the optimal solution. – tmyklebu Dec 14 '13 at 21:03

2 Answers2

4

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.

  1. 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.

  2. 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.

tranquil
  • 499
  • 7
  • 13
2

How to determine the longest increasing subsequence using dynamic programming?

Please read my explanation there first. If it is still not clear, read the following:

The algorithm keeps the lowest possible ending number for LIS of every length. By keeping the lowest numbers, you can extend the LIS in a maximal way. I know this is not a proof, but maybe it will be intuitive for you.

Community
  • 1
  • 1
Petar Minchev
  • 46,889
  • 11
  • 103
  • 119