[백준] 2491 수열 - DP JAVA

https://www.acmicpc.net/problem/2491

2491번: 수열

코드설명

DP 문제입니다.

 

문제로직입니다.

1. increaseDp 배열은 주어진 배열에서 각 인덱스까지의 최대 증가하는 부분 배열의 길이를 저장하고, decreaseDp 배열은 최대 감소하는 부분 배열의 길이를 저장합니다.

2. 배열을 순회하면서 현재 원소와 이전 원소를 비교하여 증가 또는 감소하는 부분 배열의 길이를 계산합니다. 만약 현재 원소가 이전 원소보다 크다면 증가 부분 배열의 길이를 1 증가시키고, 작다면 감소 부분 배열의 길이를 1 증가시킵니다. 이를 increaseDp와 decreaseDp 배열에 저장합니다.

3. 최대 길이를 찾기 위해 max 변수를 사용하여 increaseDp와 decreaseDp 배열의 각 인덱스에 대해 최대값을 계산합니다.

 

연속하여 증가하는 부분 배열과 연속하여 감소하는 부분배열 DP를 따로 선언하여 구하면 됩니다.

코드

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

public class Main {
	public static int N;
	public static int[] arr = new int[100001];
	public static long[] decreaseDp = new long[1000001];
	public static long[] increaseDp = new long[1000001];
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	increaseDp[0] = 1;
    	decreaseDp[0] = 1;
    	for(int i=1;i<N;i++) {
    		if(arr[i-1] <= arr[i]) {
    			increaseDp[i] = increaseDp[i - 1] + 1;
    		}else {
    			increaseDp[i] = 1;
    		}
    		
    		if(arr[i-1] >= arr[i]) {
    			decreaseDp[i] = decreaseDp[i-1] + 1;
    		}else {
    			decreaseDp[i] = 1;
    		}
    		
    	}
    	
    	long max = 0;
    	for(int i=0;i<N;i++) {
    		max = Math.max(max, Math.max(increaseDp[i], decreaseDp[i])); 
    	}
    	System.out.println(max);
    	
    }
	
}