```
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if(n<2)
return n;
vector<int> DP(n, 1); // dynamic programming
// DP[i] denotes the length of the longest increasing sequence
// in nums[0,1,2,i] with nums[i] as the ending element
int i, j;
for(i=1; i<n; i++)
{
for(j=0; j<i; j++)
{
if(nums[i] > nums[j])
DP[i] = max(DP[i], DP[j]+1);
}
}
int result=0;
for(i=0; i<n; i++)
{
result = max(result, DP[i]);
}
return result;
}
};
```