[백준 2104번] 부분배열 고르기 (Python3)

N,data = int(input()),[*map(int,input().split())]+[0]

presum = [0]
for i in range(N):
  presum.append(presum[-1]+data[i])

stack,result = [],0
for i in range(N+1):
  h = data[i]
  j = i
  while stack and stack[-1][0]>=h:
    h1,j = stack.pop()
    result = max(result,(presum[i]-presum[j])*h1)
  stack.append((h,j))
print(result)

히스토그램 [백준 6549번] 히스토그램에서 가장 큰 직사각형 (Python3) (tistory.com) 문제의 변형문제이다.

히스토그램은 (구간의 높이의 최소)*(구간의 너비) 의 최댓값을 구했다면, 이 문제는 (구간의 높이의 최소)*(구간의 합) 의 최댓값을 구해준다.

 

따라서 히스토그램 문제와 똑같이 풀되, result를 갱신하는 과정에서 H*(i-j)를 하는것이 아닌, H*(presum[i]-[j])를 해주면 된다. (presum은 누적합이다)

 

 

오늘의 교훈) 히스토그램 문제는 다양하게 활용할 수 있다.