class Solution {
    public int lengthOfLIS(int[] nums) {

        int result = Integer.MIN_VALUE;

        // dp[rounds][i_ending_target]
        int[] dp = new int[nums.length];

        // 1st row (initialize)
        for (int target = 0; target < dp.length ;target++) {
            dp[target] = 1; //
        }

        for (int target = 0; target < dp.length ;target++) {
            int best_route = 0;
            for (int j = 0; j < target ;j++) {
                if (nums[target] > nums[j]) {
                    best_route = Math.max(best_route, dp[j]);
                }
            }
            dp[target] += best_route;

            // System.out.println(Arrays.toString(dp));

            result = Math.max(result, dp[target]);
        }

        return result;
    }
}