Longest Increasing Subsequence

코테 문제

https://leetcode.com/problems/longest-increasing-subsequence/

코테 풀이 & 설명

```java
class Solution {
    Map<Integer, Integer> memo = new HashMap<>();
    int[] nums;

    public int lengthOfLIS(int[] nums) {
        this.nums = nums;
        int max = 0; // 각 경로별로 count가 따로 있어야 하므로 지역변수로 선언하기

        for (int i = 0; i<nums.length; i++) { // ArrayIndexOutOfBoundsException이 애초에 나지 않도록 여기서 잡고 시작하기
            max = Math.max(max, result(i)); // 현재 가장 큰 값과 다음 값을 비교하기 위해서 이렇게 하기
        }
        return max;
    }

    int result(int index){
        if (memo.containsKey(index)) return memo.get(index); // 했던거 다시 하지 않기 위해서 앞에서 미리 확인하기

        int maxLen = 1; // 답이 적어도 1 이상이기 때문에 값을 선언해준것. 여기서 시작할 수 있도록. 이 값으로 update 해준다.

        for (int next = index+1; next <nums.length; next++) { // 1부터 시작한다는 의미
            if (nums[next] > nums[index]) { // 다음꺼 값이 더 크다면
                maxLen = Math.max(maxLen, 1 + result(next)); // count++가 아니라 이렇게 1씩 더해서 값을 구하는 방식
            }
        }

        memo.put(index, maxLen);
        return maxLen;
    }
}
```