코테 공부
[DP]조 짜기(백준 2229번, 자바)☆☆☆☆☆
DaEun_
2022. 12. 20. 21:41
2229번: 조 짜기
알고스팟 캠프에 N(1 ≤ N ≤ 1,000)명의 학생들이 참여하였다. 학생들은 열심히 공부를 하고 있었는데, 어느 날 조별 수업을 진행하기로 하였다. 조별 수업의 목적은 잘 하는 학생들과 덜 잘 하는
www.acmicpc.net
원리를 이해해도 코드로 풀어낸다는게 제일 어려웠던 문제,,,
import java.util.*;
class Solution {
static int N;
static int[] d;
static int[] dp;
public static void main(String args[]) {
int max;
int min;
Scanner sc=new Scanner(System.in);
N=sc.nextInt();
d=new int[N+1];
dp=new int[N+1];
for(int i=1;i<=N;i++) {
d[i]=sc.nextInt();
max=Integer.MIN_VALUE;
min=Integer.MAX_VALUE;
for(int j=i;j>0;j--) {
if(max<d[j]) max=d[j];
if(min>d[j]) min=d[j];
dp[i]=Math.max(dp[i], max-min+dp[j-1]);
}
}
System.out.println(dp[N]);
}
}