[Ch.10 - DP] 03. 최대 부분 증가수열 [+LIS]

3. 최대 부분 증가수열

 

설명

N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라.

예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어

길이가 5인 최대 부분 증가수열을 만들 수 있다.

입력

첫째 줄은 입력되는 데이터의 수 N(3≤N≤1,000, 자연수)를 의미하고,

둘째 줄은 N개의 입력데이터들이 주어진다.

출력

첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.

예시 입력 1 

8
5 3 7 8 6 2 9 4

예시 출력 1

4

---

dy[i] : 수열에서 i번째 숫자를 마지막으로 하는 최대 증가 수열의 길이

dy[3]이면, 8을 마지막 항으로 하는 최대 증가 수열 길이

 

dy[0]이면, 수열의 길이가 1이므로 -> 1

 

dy[1]이면, 마지막 항이 3인데, 5는 3보다 크므로, -> 1

 

dy[2]이면, 7을 마지막으로 하는 수열의 길이

직전항이 3일 경우, dy[1]+1=2

직전항이 5일 경우, dy[0]+1=2

-> dy[0]+1이 dy[1]+1보다 크지 않으므로, dy[2]=dy[1]+1

 

dy[3]이면, 8을 마지막으로 하는 수열의 길이

직전항이 7인 경우, dy[2]+1=3

직전항이 3인 경우, dy[1]+1=2

직전항이 5인 경우, dy[0]+1=2

-> dy[3]=dy[2]+1

 

dy[4]이면, 6보다 큰 7,8은 직전항이 불가능하므로,

직전항이 3인 경우, dy[1]+1=2

직전항이 5인 경우, dy[0]+1=2

-> dy[4]=dy[1]+1

 

dy[5]이면, 2보다 작은 항이 존재하지 않으므로, dy[5]=1

dy[6]이면, dy[3]+1=4

dy[7]이면,

직전항이 2인 경우 dy[5]+1=2

직전항이 3인 경우 dy[1]+1=2

-> dy[7]=dy[5]+1

 

answer는 dy배열에서 가장 큰값

-> answer는 1로 초기화해야 한다.

-> 최대 크기 길이가 1일수도 있기 때문에

 

---

 

 

package dynamic.ch10;

import java.util.Scanner;
//최장 증가 부분 수영
//LIS : Longest Increasing Subsequence

public class Dynamic03 {
	static int[] arr;
	static int[] dy;
	static int solution(int n) {
		dy=new int[n];
		dy[0]=1;
		int max=1;
		for(int i=1;i<n;i++) {	
			for(int j=i-1;j>=0;j--) {
				if(arr[i]>arr[j]&&dy[i]<=dy[j])
					dy[i]=dy[j]+1;
				if(max<dy[i]) max=dy[i];
			}
			if(dy[i]==0) dy[i]=1;
		}
		
		
		return max;
	}
	public static void main(String[] args) {
		Scanner kb= new Scanner(System.in);
		int n=kb.nextInt();
		arr=new int[n];
		for(int i=0;i<n;i++) {
			arr[i]=kb.nextInt();
		}
		System.out.println(solution(n));
	}

}

import java.util.*;

public class Main {
  static int [] arr;
  static int n, answer=1;
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    n = in.nextInt();
    arr = new int[n];
    for(int i=0;i<n;i++){
      arr[i]=in.nextInt();
    }
    System.out.println(solution(arr));
  }
  static int solution(int[] arr){
    int[] dy = new int[n];
    dy[0]=1;
    for(int i=1;i<n;i++){
      for(int j=i-1;j>=0;j--){
        if(arr[j]<arr[i] && dy[i]<=dy[j]) {
          dy[i]=dy[j]+1;
          answer=Math.max(answer, dy[i]);
        }
      }
      if(dy[i]==0) dy[i]=1;
    }
    return answer;
  }
}

 

+) 세련된 풀이

package dynamic.ch10;

import java.util.Scanner;

public class Dynamic03_R {
	static int[] dy;
	static int solution(int[] arr) {
		int answer=0;
		dy=new int[arr.length];
		dy[0]=1;
		//n이 1인 경우 예외처리
		answer=dy[0];
		
		for(int i=1;i<arr.length;i++) {
			int max=0;
			//i번째가 가장 작을 경우 ->max=0이 되고, +1해야하므로
			for(int j=i-1; j>=0;j--) {
				if(arr[j]<arr[i]&& dy[j]>max) max=dy[j];
			} 
			dy[i]=max+1;
			answer=Math.max(answer, dy[i]);
		}
		
		return answer;
	}
	public static void main(String[] args) {
		Scanner kb= new Scanner(System.in);
		int n=kb.nextInt();
		int[] arr= new int[n];
		for(int i=0;i<n;i++) {
			arr[i]=kb.nextInt();
		}
		System.out.println(solution(arr));
		
	}

}