https://www.acmicpc.net/problem/11055
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
int[] dp = new int[n]; // 증가 부분 수열의 합
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
dp[0] = arr[0];
int answer = dp[0];
for(int i=1; i<n; i++){
int max = 0;
for(int j=i-1; j>=0; j--){
if(arr[i] > arr[j] && dp[j] > max){
max = dp[j];
}
}
dp[i] = max + arr[i];
answer = Math.max(answer, dp[i]);
}
System.out.println(answer);
}
}
https://yeoncoding.tistory.com/597
가장 긴 증가 부분 수열 문제랑 비슷하다.
그런데 이번에는 증가 부분 수열의 합을 dp에다 저장해야 한다.
그러므로 arr배열의 i번째보다 작은 j번째 값들 중에 dp[j]의 최댓값을 골라
dp[i]에 그 최댓값과 arr[i] 를 더한 값을 저장한다.
'ALGORITHM' 카테고리의 다른 글
[JAVA] 백준 11054번- 가장 긴 바이토닉 부분 수열 (0) | 2022.11.07 |
---|---|
[JAVA] 백준 11722번- 가장 긴 감소하는 부분 수열 (0) | 2022.11.07 |
[JAVA] 백준 11057번- 오르막 수 (0) | 2022.11.06 |
[JAVA] 백준 1309번- 동물원 (0) | 2022.11.04 |
[JAVA] 백준 2225번- 합분해 (0) | 2022.11.03 |