자석

풀이

 처음에는 문제 유형으로 n개의 칸 중 2개를 선택해서 주어진 조건에 따라 연산을 수행하는 조합이 떠올랐다. 2개를 선택하므로 이중 for 문을 사용해서 문제를 풀었으나 시간초과 판정을 받았다. 이중 for 문이 O(n^2)의 시간복잡도를 가지므로 적어도 O(n), O(nlogn)이 가능한지 생각해봤다. 아쉽게도 적당한 아이디어가 떠오르지 않아서 결국 구글링했다.
이 문제는 주어진 조건을 살짝 다듬어야 해답이 보인다. 문제의 조건을 풀어쓰면 아래와 같다.

• n > s일 경우

  En - Es -k(n - s)
  = En - Es -kn + ks
  = En - kn -(Es - ks)

 즉 En-kn의 최대값, Es-ks의 최소값을 구하면 된다. 여기서 En-kn와 Es-ks는 서로 독립이다. 따라서 for 문으로 순차탐색 하면서 그 지점에서 Ei-ki 값을 구해서 최소 최대를 갱신해주면 된다. n < s일 경우에는 리스트를 역정렬해서 앞선 과정을 반복하면 된다.

n, k = map(int, input().split())
data = list(map(int, input().split()))

first_answer = -10e10
min_value = data[0]-k
for i in range(1, n):
    first_answer = max(first_answer, data[i]-(i+1)*k-min_value)
    min_value = min(min_value, data[i]-(i+1)*k)

# n극 s극 바꿔서 생각 -> 리스트 역순 정렬
data.reverse()
second_answer = -10e10
min_value = data[0]-k
for i in range(1, n):
    second_answer = max(second_answer, data[i]-(i+1)*k-min_value)
    min_value = min(min_value, data[i]-(i+1)*k)

print(max(first_answer, second_answer))

시간복잡도 : O(n)