사용한 것
- 증가 구간 중 최대 값을 찾기 위한 bottom-up
풀이 방법
num
에 비교한 숫자를 저장하되 num
보다 작은 값은 비교 X(이미 비교한 인덱스에 포함되어있음)
코드
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 = Stream.of(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
int[] dp = new int[N];
for (int i = 0; i < N; i++) {
dp[i] = arr[i];
int num = 0;
for (int j = i - 1; j >= 0; j--) {
if (arr[i] > arr[j] && arr[j] > num) {
dp[i] = Math.max(arr[i] + dp[j], dp[i]);
}
}
}
int answer = dp[0];
for(int i = 1; i < N; i++) {
answer = Math.max(dp[i], answer);
}
System.out.println(answer);
}
}