가장 긴 바이토닉 부분 수열

이 문제는 가장 긴 증가하는 부분 수열의 응용문제다.

문제를 보면 알겠지만, 증가하다가 감소하는 경향을 가진 가장 긴 부분 수열을 찾으면 된다.

숫자가 어떤 특정한 최댓값을 기점으로 증가하다가 감소하게 될테니, 이 최댓값을 기점으로 증가하는 수열의 길이와 감소하는 수열의 길이의 합이 최대인 값을 구하는 문제라는 것을 눈치챌 수 있을 것이다.

답

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func init() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
}

func scanInt() int {
    sc.Scan()
    ret, _ := strconv.Atoi(sc.Text())
    return ret
}

func main() {
    n := scanInt()
    arr := make([]int, n)
    inc := make([]int, n)
    dec := make([]int, n)

    for ni := 0; ni < n; ni++ {
        arr[ni] = scanInt()
        inc[ni] = 1
        dec[ni] = 1
    }

    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            if arr[i] > arr[j] {
                inc[i] = max(inc[i], inc[j]+1)
            }
        }
    }

    for i := n-1; i >= 0; i-- {
        for j := i+1; j < n; j++ {
            if arr[i] > arr[j] {
                dec[i] = max(dec[i], dec[j]+1)
            }
        }
    }

    ans := 0
    for i := 0; i < n; i++ {
        // 1을 빼야한다. 변곡점이 되는 값이 두 번 더해졌기 때문!
        ans = max(ans, inc[i]+dec[i]-1)
    }

    fmt.Print(ans)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}