Simple O(n^2) DP solution


#1
int Solution::lis(const vector<int> &nums) {
    int maxlen = 0;
    vector<int> dp(nums.size(), 0);
    
    if(nums.size() <= 1) return nums.size();
    
    dp[0] = 1;
    
    for(int i = 1; i < nums.size(); i++){
        int longest = 0;
        for(int j = 0; j < i; j++){
            if(nums[j] < nums[i]){
                if(dp[j] > longest){
                    longest = dp[j];
                }
            }
        }
        dp[i] = longest + 1;
    }
    
    for(int i = 0; i < dp.size(); i++){
        maxlen = max(maxlen, dp[i]);
    }
    
    return maxlen;
}