[伯俊]ニック号部分の数列をお願いします

1.質問

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

2.近接

まず,この問題は成長が最も長い部分数列問題を解決してこそ,近づくことができる.最長の部分数列問題と最長の部分数列問題が統合されているからだ.

最大増分部分数列

まず、この問題はDPによって解決することができる.{1 3 2 4 5}と同じ配列の場合、for文を使用してインデックスよりも小さいダブルfor文を回転します.これにより最小値を求めることができるが,長さが最も長い前の値+1である.難しいですが、例を見てみましょう.

です.

인덱스       0 1 2 3 4
주어진 배열값 1 3 2 4 5
수열 길이    1
-> 인덱스가 0일 때는 이전에 값이 없으니 수열 길이가 1이다

인덱스       0 1 2 3 4
주어진 배열값 1 3 2 4 5
수열 길이    1 2
-> 인덱스가 1, 배열값이 3인 경우 인덱스 0~0을 보자
-> 3보다 작은 배열 값 1만이 존재하고 그 때 수열길이가 1이므로 2(1+1)이 배열값 3의 최대 수열길이다.

인덱스       0 1 2 3 4
주어진 배열값 1 3 2 4 5
수열 길이    1 2 2
-> 인덱스가 2, 배열값이 2인 경우 인덱스 0~1(2-1)을 보자
-> 2보다 작은 배열 값은 1만이 존재하고 그 때 수열길이가 1이므로 2(1+1)이 배열값 2의 최대 수열길이다.

인덱스       0 1 2 3 4
주어진 배열값 1 3 2 4 5
수열 길이    1 2 2 3
-> 인덱스가 3, 배열값이 4인 경우 인덱스 0~2(3-1)을 보자
-> 4보다 작은 배열 값은 1, 3, 2가 존재하고 그 때 수열길이 최대는 2이므로 3(2+1)이 배열값 4의 최대 수열길이다.

인덱스       0 1 2 3 4
주어진 배열값 1 3 2 4 5
수열 길이    1 2 2 3 4
-> 인덱스가 4, 배열값이 5인 경우 인덱스 0~3(4-1)을 보자
-> 5보다 작은 배열 값은 1, 3, 2, 4가 존재하고 그 때 수열길이 최대는 3이므로 4(3+1)이 배열값 5의 최대 수열길이다.

以上の方法で解き、時間の複雑さはO(n^2)ですが、直感的な方法なので分かりやすいです.

事実上,この方法に二分探索を適用し,O(Nlogn)で求めることができる.しかし,この方法では数列の長さの配列を求めることができないため,ここでは用いない.

この方法を用いて成長が最も長い部分数列を求めることができ、反転配列も成長が最も長い部分数列を求めることができる.

2個の数列の長さの数列を加算した後に、最大値-1を求めて解答がありました

−1が行われたのは,このインデックスが2回繰り返されたためである.

3.コード

n = int(input())
arr = list(map(int,input().split()))

# 가장 긴 증가하는 부분 수열
up = []
for i in range(n):
  num = arr[i]
  up_max = 0
  for j in range(i):
    if arr[j] < num:
      up_max = max(up_max, up[j])
  up.append(up_max+1)
# 가장 긴 감소하는 부분 수열
down = []
for i in range(n-1,-1,-1):
  num = arr[i]
  down_max = 0
  for j in range(i+1,n):
    if arr[j] < num:
      down_max = max(down_max, down[n-1-j])
  down.append(down_max+1)
print(max([a+b for a,b in zip(up, down[::-1])])-1)