백준 11055 가장 큰 증가 부분 수열 (JAVA 자바 풀이)

백준 11055 가장 큰 증가 부분 수열 (JAVA 자바 풀이)

 

---

 

 

📌 문제 

수열 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의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

 

 

 

 

---

 

 

 

💎 문제 분석

 

 

LIS가 되는 조건이 추가된 부분이다. lis 이면서 dp값이 더 커지는 경우, 두 가지 조건을 만족시킬 때 초기화를 시켜준다. 

 

메서드를 별도로 만들기 위해 변수들을 Field로 올렸다. 

 

 

 

💡 코드 구현

 

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

public class Main {

	private static int[] numbers;
	private static int[] dp;

	public static void main(String[] args) throws IOException {

		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(bufferedReader.readLine());

		dp = new int[1001];
		numbers = new int[1001];
		StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		for (int i = 1; i <= N; i++) {
			int number = Integer.parseInt(stringTokenizer.nextToken());
			numbers[i] = number;
			dp[i] = number;
		}

		int sumMax = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j < i; j++) {
				if (isLis(i, j) && isSumAsMax(i, j)) {        // lis 이면서도 더했을 때 더 커야 되므로
					dp[i] = dp[j] + numbers[i];
				}
			}
			sumMax = Math.max(sumMax, dp[i]);
		}

		System.out.println(sumMax);
	}

	private static boolean isSumAsMax(int i, int j) {
		return dp[i] < dp[j] + numbers[i];
	}

	private static boolean isLis(int i, int j) {
		return numbers[i] > numbers[j];
	}
}