백준 | 11055번. 가장 큰 증가하는 부분수열 - DP 문제

⬛ 백준 11055번. 가장 큰 증가하는 부분수열

https://www.acmicpc.net/problem/11055

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

문제

수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.

---

💚나의 풀이

DP 풀이 모습

• i로 현재 데이터 arr[i]를 찍고, j는 i부터 0까지 역순으로 앞을 돌면서, 현재 i번쨰 데이터보다 값은 작으면서, dy[j] 중에선 가장 큰 합에 현재의 arr[i]값을 더하는 방식으로 구했다.

package to_0801_2;

import java.util.Scanner;

//11055번. 가장 큰 증가하는 부분수열 
public class Main {
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		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();
		
		int[] dy = new int[n];
		dy[0] = arr[0];//초기화 
	
		for(int i=1; i<n; i++) { //i로 현재값 찍고 
			int max = 0;
			for(int j=i; j>=0; j--) {//j로 i앞을 순회할 거임 
				if(arr[i] > arr[j] && max < dy[j]) {
					max = dy[j];//갱신 계속 시켜줘서 최대 값으로 세팅하려고 
				}
			}
			//빠져나온 상태에서 dy[i] 세팅해주기 
			dy[i] = max+arr[i];//기존 max값에 현재 데이터i도 붙여서 dy[i] 담기 
			
		}
		int max = Integer.MIN_VALUE;
		for(int x : dy) {
			max = Math.max(max, x);
		}
		System.out.println(max);
	}
}