G2229. 조 짜기

문제

제출 코드

• 사용 알고리즘 : DP

• 주어진 숫자를 하나씩 읽어가면서, dp배열에 i번째 수까지 고려했을 경우 점수 최대값을 저장

• i번째 수부터, 역순으로 고려할 숫자를 하나씩 늘려가면서 i번째 수가 포함된 마지막 조의 점수를 계산해준다 → 마지막 조 점수 + 이전 조 최대점수(dp[j-1]) ⇒ 최대값을 현재 dp에 저장

  

package gold;

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

public class G2229_makeGroup {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] df = new int[N], num = new int[N];

		String[] ch = br.readLine().split(" ");
		num[0] = Integer.parseInt(ch[0]);
		int result = 0;

		for(int i=1; i<N; i++) {
			num[i] = Integer.parseInt(ch[i]);
			int min=num[i], max=num[i];
			df[i]=df[i-1];
			for(int j=i-1; j>=0; j--) {
				min = Math.min(min, num[j]);
				max = Math.max(max, num[j]);
				df[i] = Math.max(((j==0)?0:df[j-1])+max-min, df[i]);
			}
			result = Math.max(result, df[i]);
		}
		System.out.println(result);
	}
}