2018/05 썸네일형 리스트형 BOJ)15673 헤븐스 키친2 문제 :http://icpc.me/15673 n개의 수열이 주어질 때, 연속 된 두 구간을 선정을 한다. 두 구간을 a,b라하면 구간 a의 합과 구간 b의 합의 곱의 최댓값을 구하는 문제이다. 생각해보면 구간 a의 합과 구간 b의 합의 최솟값들을 곱하는 경우와, 구간 a의 합과 구간 b의 합의 최댓값들을 곱하는 경우가 답의 후보가 됨을 알 수 있다. 구간 a가 i~j 구간 b가 k~l 이라고 해보자. k를 고정시킨 뒤 생각해보면 구간 k~l의 합은 psum[l]-psum[k-1]이므로, k보다 크거나 같은 범위의 psum의 최댓값과 최솟값을 가지고 있으면, 구간 b의 최댓값과 최솟값을 구할 수 있다. 그럼 i~j 구간의 최댓값과 최솟값은 어떻게 처리할 수 있을까? 구간 i~j의 합은 psum[j]-psu.. 더보기 이전 1 다음