300. Longest Increasing Subsequence

class Solution {public:    int lengthOfLIS(vector<int>& nums) {        std::vector<int> best_so_far(nums.size());        int best = 1;        for (int i = 0; i < nums.size();             i++) {  // loop through each possible number, want to figure                     // out the longest increasing subsequence at each                     // index.            best_so_far[i] =                1;  // initialized each element to 1, as that is the                    // default best subsequence length at each place. this                    // is going to get treated like best possible value so                    // far.            for (int k = 0; k < i;                 k++) {  // now go through all numbers before the index we                         // are trying to compute.                if (nums[k] <                    nums[i]) {  // the most basic check is to figure out if                                // some element being compare is less than                                // the element that we have.                    // since we have memoized each element to store its                    // best sequence length at each location, we just call                    // that back if we find that the element is less than                    // the current element and then either go with that or                    // the best possible length we have so far.                    best_so_far[i] = max(                        best_so_far[k] + 1,                        best_so_far[i]);  // if it is, then we either add                                          // such element to our increasing                                          // list or we keep the best known                                          // value so far.                    best = max(best, best_so_far[i]);                }            }        }        for (int i = 0; i < nums.size(); i++) {            std::cout << best_so_far[i] << " ";        }        return best;    }};