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

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

---

풀이

LIS(최장 증가 수열)을 응용하여 해결했습니다.

LIS(최장 증가 수열)처럼 증가하는 긴 수열을 구하는 것은 동일하지만 이때, 합이 가장 큰 수열을 구해야 한다는 점을 주의해야 합니다.

---

코드

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

public class Main {
	public static int N, answer;
	public static int[] A = new int[1001];
	public static int[] memo = new int[1001];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 1; i <= N; ++i) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		
		for (int i = 1; i <= N; ++i) {
			memo[i] = A[i];
			
			for (int j = 1; j < i; ++j) {
				if (A[i] > A[j] && memo[i] < memo[j] + A[i]) {
					memo[i] = memo[j] + A[i];
				}
			}
		}
		
		for (int i = 1; i <= N; ++i) {
			answer = (answer < memo[i]) ? memo[i] : answer;
		}
		
		System.out.println(answer);
	}
}

---

 

pyo7410/Algorithm