Find the Longest Increasing Sub-sequence -- LeetCode 300

[Question]
Given an array of integers A of length n, find the longest sequence i1, i2, ... ik such that ij < ij+1 and A[ ij ] < A[ ij+1 ] for any j, 0<j<k.

For example, {1,3,5,2,7} --> {1,3,5,7} and {0,5,1,2,6,4} --> {0,1,2,4}.

[Analysis]

This is a classic Dynamic Programming (DP) case. A solution is given in book "Algorithm For Interviews". 

First, we define a function of Si, which refers the longest sequence that ends at A[i]. Then, Si is equal to the longest Sj +1, when j<i and A[j]<A[i].

Using a table, the algorithm can populate S[i] from 0 to the end of array A (S0 = 1). 

Note: 

1) To find the longest increasing consecutive sub-sequence would be simpler. DP is not needed.

2) There are a few other questions derived from this: e.g. find longest common sub-strings between two strings; or find the longest palindromic sub-sequence.

[Solution]

List<Integer> findLongestIncreasingSequence(int[] a) {
int[] s = new int[a.length];
int[] prev= new int[a.length];  //used to retrieve the list.

s[0] = 1;
for (int i=0; i<prev.length; i++) prev[i] =-1;

int maxLength =0;
int maxEndIndex =0;

for (int i=1; i<a.length; i++) {
for (int j=0; j<i; j++) {
if (a[i]>a[j] && s[i]<s[j]+1) {
s[i] = s[j]+1;
prev[i] = j;
}
}

if (s[i]>maxLength) {
maxLength = s[i];
maxEndIndex = i;
}
}

int i=maxEndIndex;
List<Integer> list = new ArrayList<Integer>();
while (prev[i] != -1) {
list.add(a[i]);
i = prev[i];
} 
list.add(a[i]);
return list;
}

//
// -- O(NLogN) ---
//
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> res;
        for (auto& n: nums) {
            auto it = lower_bound(res.begin(), res.end(), n);
            if (it==res.end()) res.push_back(n);
            else *it = n;
        }
        return res.size();
    }

};