11054번 가장 긴 바이토닉 부분 수열 BOJ 백준 C언어

문제

수열 S가 어떤 수 Sk를 기준으로 S1< S2< ... Sk-1< Sk> Sk+1> ... SN-1> SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20,30, 25, 20}과 {10, 20, 30,40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

구현

바이토닉 수열의 중점은
1. 앞에서 뒤로 부분 수열을 한 번 찾고
2. 뒤에서 앞으로 부분 수열을 한 번 찾은 후
3. 해당 배열값들의 합중 가장 큰 값을 찾는것이다.

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define _CRT_SECURE_NO_WARNINGS

int compare(int a, int b) {
    return (a > b) ? a : b;
}

int main(void) {
    int num, i, j, result = 0, max = 0;
    int arr[1001] = { 0 };
    int dp1[1001] = { 0 };
    int dp2[1001] = { 0 };
    scanf("%d", &num);

    for (i = 1; i <= num; i++) {
        scanf("%d", &arr[i]);
    }

    for (i = 1; i <= num; i++) { //앞에서 뒤 가장 긴 증가하는 부분 수열 찾기
        max = 0;
        for (j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                if (dp1[j] > max) {
                    max = dp1[j];
                }
            }
        }
        dp1[i] = max + 1;
    }

    for (i = num; i > 0; i--) { //뒤에서 앞으로 가장 긴 증가하는 부분 수열 찾기
        max = 0;
        for (j = num; j > i; j--) {
            if (arr[i] > arr[j]) {
                if (dp2[j] > max) {
                    max = dp2[j];
                }
            }
        }
        dp2[i] = max + 1;
    }

    for (i = 1; i <= num; i++) { // 각 dp배열을 앞에서 뒤로 탐색하면서
        if (result < dp1[i] + dp2[i] - 1) { // 배열 값의 합산 - 1 이 가장큰 값 찾기
            result = dp1[i] + dp2[i] - 1;
        }
    }

    printf("%d", result);
}