Longest Increasing Subsequence C++ Implementation

Problem is to find the length of the longest increasing sequence from given sequence. We will also print longest sequence, if there are more than one longest sequence with same length we will print one of the sequence.

You can find more details of the problem at wiki: Longest_increasing_subsequence

This is purely my understanding of implementation of longest increasing subsequence DP solution, if you may find it in-efficient please comment.

void LongestIncreasingSubSequence(vector<int> input){     vector<int> storage(input.size());     vector<int> sequence(input.size());          int maxSeq = 0;     for (int i=0; i < input.size(); i++) {         int maxSoFar = 0;         sequence[i] = i;         for (int j = 0; j < i; j++) {             if(input[i] > input[j] && maxSoFar < storage[j]){                 maxSoFar = storage[j];                 sequence[i] = j;             }         }         storage[i] = maxSoFar+1;         if (storage[i] > maxSeq) {             maxSeq = storage[i];         }     }          int i = (int)input.size();     for (; i >= 0; i--) {         if (storage[i] == maxSeq) {             cout << input[i] << " ";             break;         }     }          while (sequence[i] != i) {         cout << input[sequence[i]] << " ";         i = sequence[i];     }     cout << endl;       }

The sequence will be printed in reverse order, you can use stack or temporary storage for printing the sequence in required order.