2104

[알고리즘] 백준 2104 - 부분 배열 고르기

문제본문 문제해설 문제에서의 N의 범위는 100,000 이하입니다. 따라서 N^2 인 완전탐색으로는 시간초과가 발생할 수 있습니다. 분할 정복은 문제의 범위를 2이상으로 나누어 부분적으로 정복하여 푸는 방법입니다. 최대의 점수를 갖는 부분배열을 구하는 이 문제에 적용하여 중앙 값을 기준으로 3가지 경우에서 최대값을 구하면 됩니다. 1. 중앙값을 포함하는 부분 배열 이 경우는 중앙 값을 포함하는 부분 배열의 점수를 구하는 방법입니다. 히스토그램 풀이법과 유사하고 처음 중앙값하나 존재하는 배열에서 왼쪽, 또는 오른쪽으로 하나씩 요소들을 포함시키면서 최대값을 찾는 방법입니다. 왼쪽이나 오른쪽으로 이동하는 기준은 부분배열의 점수 공식을 참고하면 큰 요소를 포함하는 것이 무조건 최대 점수로 가는 길이 됩니다. 그..