2022.02.08 [백준] C# 가장 긴 바이토닉 부분 수열

 

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

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

 

---

풀이

이 문제는 1~n까지의 LIS를 구해서 upper배열에 저장하고 반대로 n~1까지 LIS를 구해서 lower배열에 저장했다.

num의 배열에 순서대로 하면 최장 증가수열이고, 반대로 하면 최장 감소 수열이기 때문이다.

그리고 upper[i] + lower[i] -1 (-1을 해주는 이유는 i가 겹치기 때문)을 해주어 답을 구했다.

using System;
using System.Text;
using System.IO;
 
class Program
{
    static int[] num;
    static int[] upper;
    static int[] lower;
 
    static void Cal(int n)
    {
        for(int i = 2; i <= n; i++)
        {
            for(int j = 1; j < i; j++)
            {
                if (num[i] > num[j])
                {
                    upper[i] = Math.Max(upper[i], upper[j]+1);
                }
            }
            
        }
        for(int i = n-1; i > 0; i--)
        {
            for(int j = n; j > i; j--)
            {
                if (num[i] > num[j])
                {
                    lower[i] = Math.Max(lower[i], lower[j]+1);
                }
            }
            
        }
        
    }
 
    static void Main()
    {
        StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
        StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
        StringBuilder sb = new StringBuilder();
        int n = int.Parse(sr.ReadLine());
        num = new int[n + 1];
        upper = new int[n + 1];
        lower = new int[n + 1];
        string[] s = sr.ReadLine().Split();
        for(int i = 1; i <= n; i++)
        {
            num[i] = int.Parse(s[i - 1]);
            upper[i] = 1;
            lower[i] = 1;
        }
        Cal(n);
        int max = 0;
        for(int i = 1; i <= n; i++)
        {
            max = Math.Max(max, upper[i] + lower[i]);
        }
        sw.WriteLine(max - 1);
        sr.Close();
        sw.Close();
    }
}