LeetCode/cpp/longest-increasing-subsequence.cpp

#include <algorithm>
#include <vector>

class Solution {
  public:
    int lengthOfLIS(const std::vector<int> &nums) {
        if (nums.empty()) {
            return 0;
        }

        std::vector<int> dp(nums.size(), 1);
        int m = 1;

        for (auto i = 1u; i < nums.size(); ++i) {
            for (auto j = 0u; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    dp[i] = std::max(dp[i], 1 + dp[j]);
                    m = std::max(m, dp[i]);
                }
            }
        }

        return m;
    }
};