dp

15779 Zigzag

아 이거 dp로 풀었는데 아니라네? ㅋㅋ 띠용~!? 시간초과도 아닌 틀렸습니다~? 앵
Longest Zig-Zag Subsequence
스택오버플로

n=int(input())
l=list(map(int,input().split()))
low,high=[1]*n,[1]*n
m=0

for i in range(1,n):
  for j in range(i):
    if l[j] > l[i]:
      low[i] = max(low[i],high[j]+1)
    elif l[j] < l[i]:
      high[i] = max(high[i],low[j]+1)

  t=max(low[i],high[i])
  if m < t:
    m=t
    
print(m)

아 이게 아니야? O(n)에 푸는 방법이 있다는데 다음에 읽어봐야지