[11054] - 가장 긴 바이토닉 부분 수열

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

11054번: 가장 긴 바이토닉 부분 수열

접근 방법

앞에서부터 증가하는 수열의 수를 넣는 배열하나, 뒤에서 증가하는 수열의 수를 넣는 배열 하나 생성 후, 두 배열을 더해 최대값을 찾은 후 1개가 겹치니 -1 해주기.

 

문제 풀이

• leftsum의 i 인덱스에 0~i 까지(앞에서 부터 증가) 증가된 수의 개수를 저장
• rightsum의 i 인덱스에 n-1 ~ i 까지(뒤에서부터 증가) 증가된 수의 개수 저장
• 만약 인덱스 5가 젤 크면 5에서 2개가 한번 겹치니 leftsum[5] - rightsum[5]에 -1을 더해주고 출력

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace Baekjoon.Gold
{
    class _11054
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int[] leftsum = Enumerable.Repeat(1, n).ToArray();
            int[] rightsum = Enumerable.Repeat(1, n).ToArray();

            //왼쪽에서 증가
            for(int i = 1; i<n; i++)
            {
                for(int j = 0; j<i; j++)
                {
                    if (arr[i] > arr[j])
                        leftsum[i] = Math.Max(leftsum[i], leftsum[j] + 1);
                }
            }
            //오른쪽에서 증가
            for(int i = n-2; i>=0; i--)
            {
                for(int j = n-1; j> i; j--)
                {
                    if (arr[i] > arr[j])
                        rightsum[i] = Math.Max(rightsum[i], rightsum[j] + 1);
                }
            }

            int ans = leftsum[0] + rightsum[0];
            for (int i = 1; i< n; i++)
            {
                if (leftsum[i] + rightsum[i] > ans)
                    ans = leftsum[i] + rightsum[i];
            }

            //Console.WriteLine(string.Join(" ", leftsum));
            //Console.WriteLine(string.Join(" ", rightsum));
            Console.WriteLine(ans - 1);
        }
    }
}