[Java] 백준 11055번 가장 큰 증가 부분 수열

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

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

이번 문제는 수열에 집중해서 가장 큰 합을 구하면 되는 문제입니다.

기준 숫자를 가지고 기준 숫자보다 큰 숫자들을 더해가면서 가장 큰 수열을 찾으면 됩니다.

 

package BJ;

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

public class BJ_가장큰증가부분수열 {
	static int N;
	static int[] A;
	static int[] dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		A = new int[N];
		dp = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		
		dp[0] = A[0];
		
		int result = seq();
		System.out.println(result);

	}
	private static int seq() {
		for (int i = 1; i < N; i++) {
			dp[i] = A[i];
			for (int j = 0; j < N; j++) {
				if(A[i] > A[j]) {
					dp[i] = Math.max(dp[j] + A[i], dp[i]);
				}
			}
		}
		
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < N; i++) {
			if(dp[i] > max) {
				max = dp[i];
			}
		}
		return max;
	}

}

 

Ysik Github : https://github.com/Y1sik/Algorithm/blob/main/BJ/BJ_%EA%B0%80%EC%9E%A5%ED%81%B0%EC%A6%9D%EA%B0%80%EB%B6%80%EB%B6%84%EC%88%98%EC%97%B4.java