문제

가장 긴 증가하는 부분 수열

풀이

LIS 문제를 언젠가 푼적이 있었는데 너무 안푼지 오래되서
가장 긴 수열을 정의할때 dp 배열이 가지고 있어야 되는 부분은 현재 배열에서 가장 길게 증가하는 개수를 담고있으면 된다. 마지막 배열이 가장 긴 증가 부분 수열을 가지고 있는 것도 아니기 때문에 가장 긴 증가 수열 개수를 초기화 해준다

1. 증가 수열 개수 초기화

int answer = 0; 

2. 증가 수열 개수를 갱신 한다

for (int i =0; i < n; i++) {
	dp[i] = 1; // 기본적으로 한가지의 개수를 가지고 있다
	for (int j = i - 1; j > 0; j--) {
    	if (arr[i] > arr[j]) { // 이전의 숫자보다 증가했다면
        	// dp[i] 현재까지의 증가 수열 개수
            // dp[j] + 1 이전까지의 증가 수열의 개수
        	dp[i] = Math.max(dp[i], dp[j] + 1); 
        }
    }
    answer = Math.max(dp[i], answer);
}

전체 코드

전체 코드