[Baekjoon] 11055_가장 큰 증가하는 부분 수열

Silver II

문제(출처: https://www.acmicpc.net/problem/11055)

---

< 가장 큰 증가하는 부분 수열 >

 

문제 풀이 

 

값을 차례대로 살펴보며 증가하는지 판단한다. 증가한다면 합이 더 큰지 판단한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class _11055_ { // 가장 큰 증가하는 부분 수열

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		int arr[] = new int[n];
		int sum[] = new int[n];
		st = new StringTokenizer(bf.readLine());

		for (int i = 0; i < n; i++) {
			int num = Integer.parseInt(st.nextToken());
			arr[i] = num;
			sum[i] = num;
		}

		int result = sum[0];
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				if (arr[i] < arr[j] && sum[i] + arr[j] > sum[j]) {
					sum[j] = sum[i] + arr[j];
					result = Math.max(sum[j], result);
				}
			}
		}

		System.out.println(result);
	}
}

변수)
n : 수열의 크기
arr : 수열 값
sum : 합
result : 합이 가장 큰 증가하는 부분 수열의 합

 

수열의 크기 n을 입력받는다. 수열의 크기만큼 수열 값을 입력받아 arr과  sum에 저장한다. 이중 for문을 사용하여 수열을 탐색한다. 만약 비교하는 값이 현재 값보다 크고 합도 크다면 값을 업데이트한다. 

 

최종 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.

 

* 수열의 첫 번째 값이 정답이 될 수 있으므로 result를 sum[0] 값으로 초기화한다.

---

---