Dynamic Programming

[기록용]

- 최대부분 증가수열

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

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

 

- 각 숫자가 수열의 마지막이라고 했을 때, 만들 수 있는 증가수열의 최대 길이를 기록함 

ex) arr[0] = 5 가 마지막이라고 했을 때, 만들 수 있는 증가수열의 최대길이는 1

- 앞에 자신보다 작은 수가 있으면 그 수중 max값을 가져와 +1 을 해준다

static int[] dy;
    public void solution(int[] arr){
      int answer = 0;
      dy = new int[arr.length];
      dy[0] = 1;
      //해당 숫자를 마지막이라고 했을 떄, 만들 수 있는 증가수열 길이를 넣어둠 
      for(int i=1; i<arr.length; i++){
          int max = 0;
          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]);
      }
     
    }