[JAVA] 백준 q11055 - 가장 큰 증가하는 부분 수열

11055번: 가장 큰 증가하는 부분 수열

---

> 의식의 흐름
이전에 풀었던 가장 긴 증가하는 부분 수열(https://monicajo074.tistory.com/44)이랑 완전 같은 문제네

> 풀이 과정
1. 수열의 크기(N)을 입력 받는다.
2. 수열을 배열(nums)에 입력받고 수열의 길이를 저장하는 배열(sum)을 nums[i]로 초기화한다.
3. nums[i]와 뒤쪽 수(nums[j])를 비교한다
- 만약 nums[i] < nums[j]인 경우, 증가하는 수열이 되므로 sum[j] = sum[i]+nums[j]로 변경한다.
하지만 이때 sum[j] > sum[i]+nums[j]인 경우, 가장 큰 수열을 구해야하는 것이므로 sum[j] 값을 sum[i]+nums[j]로 업데이트 하지 않고 그대로 두어야 한다. 
=> sum[j] = Math.max(sum[j], sum[i]+nums[j]);

for(int i=0;i<N-1;i++){
      int num = nums[i];

      for(int j=i;j<N;j++){
            if(num<nums[j]){
                  sum[j] = Math.max(sum[j], sum[i]+nums[j]);
            }
      }
}

 

4. 3번 과정에서 업데이트된 sum에서 가장 큰 값이 가장 큰 증가하는 부분 수열의 길이이므로 해당 값을 출력한다.

 

> 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static int N; // 수열의 크기
    public static int[] nums; // 수열
    public static int[] sum; // 증가하는 부분 수열의 합

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        nums = new int[N];
        sum = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            nums[i] = Integer.parseInt(st.nextToken());
            sum[i] = nums[i];
        }

        for(int i=0;i<N-1;i++){
            int num = nums[i];

            for(int j=i;j<N;j++){
                if(num<nums[j]){
                    sum[j] = Math.max(sum[j], sum[i]+nums[j]);
                }
            }
        }

        int max = 0;
        for(int i=0;i<N;i++){
            max = Math.max(max, sum[i]);
        }

        bw.write(Integer.toString(max));
        bw.flush();

        br.close();
        bw.close();
    }
}