보관료가 붙는 아이템 되팔기

문제

게임 아이템 거래소에서 인기 아이템 하나의 일별 시세 가 배열 prices로 주어집니다. prices[i]는 i일째의 시세입니다.

여러분은 이 아이템을 딱 한 번 사서 딱 한 번 팔 계획입니다. 단, 거래소에는 두 가지 비용이 있습니다.

• 거래 수수료 fee: 판매가 성사될 때 1회 부과됩니다.
• 보관료 hold: 아이템을 들고 있는 하루마다 부과됩니다. b일에 사서 s일에 팔았다면 보관 일수는 s - b일입니다.

즉 b일에 사서 s일에 판 경우(b < s) 순이익은 다음과 같습니다.

prices[s] - prices[b] - fee - hold × (s - b)

가능한 모든 매매 중 순이익의 최댓값 을 반환하세요. 어떻게 거래해도 순이익이 0 이하라면 거래하지 않고 0을 반환하는 solution(prices, fee, hold) 함수를 작성하세요.

예시

prices = [12, 9, 15, 11, 20, 14], fee = 2, hold = 1
→ 6
  1일에 9로 사서 4일에 20으로 팔면
  20 - 9 - 2 - 1 × 3 = 6.
  3일에 11로 사서 4일에 20으로 팔아도 20 - 11 - 2 - 1 = 6으로 같다.
 
prices = [10, 50, 11, 12], fee = 3, hold = 10
→ 27
  0일에 10으로 사서 1일에 50으로 팔면 50 - 10 - 3 - 10 = 27.
  보관료가 비싸 오래 들고 있을수록 손해다.
 
prices = [5, 9], fee = 4, hold = 1
→ 0
  유일한 거래의 순이익이 9 - 5 - 4 - 1 = -1이므로 거래하지 않는다.

제약 조건

• 1 ≤ prices.length ≤ 100,000
• 0 ≤ prices[i] ≤ 1,000,000
• 0 ≤ fee ≤ 10,000
• 0 ≤ hold ≤ 10,000
• 산 날보다 나중 날에만 팔 수 있습니다 (같은 날 사고팔 수 없습니다)
• 매수와 매도는 각각 한 번씩만 할 수 있습니다

시간 복잡도 목표: O(N)