[백준] 30618. donstructive

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

문제요약

• 순열, N(20만)
• 연속 부분 수열들이 있을 것이고, 그들의 합이 있을 것임
• 합이 최대가 되는 순열 구하기

접근법

• 연속 부분 수열들을 구해보면, 각 위치별 쓰이는 빈도가 다름
• 예를 들어 길이 5인 순열에서 각각의 부분수열에 대해서 사용되는 횟수를 카운팅해보면
• "5 8 9 8 5"
  • "5" : 1
  • "5 8" : 1 1
  • "5 8 9" : 1 1 1
  • "5 8 9 8" : 1 1 1 1
  • "5 8 9 8 5" : 1 1 1 1 1
  • "8" : x 1
  • ...
• 서로 다른 N에 대해서 구해보면 가운데를 가장 많이 사용하고 "산"처럼 카운팅이 분포됨