[알고리즘] 백준 16993

아래 정리하는 내용들은 대부분 다른 분들의 코드를 참고하여 작성한 코드이기 때문에 최적화 되어 있지 않으며 개인적으로 기억하기 위한 용도입니다. 혹시 문제 풀이를 위해서 검색하신 분들께서는 참고 수준으로만 읽어보시기 바랍니다. References https://swexpertacademy.com/ https://www.acmicpc.net/ https://leetcode.com/ 추천 블로그 https://zoosso.tistory.com/ 부분합 최대는 dp 를 이용하여 풀이가 가능하지만 세그먼트 트리를 이용한 방법도 가능하다. 대표적인 세그먼트 트리 예는 sum 값을 만드는 예가 있지만 동일한 방식으로 sum 값이 아닌 자식 노드들의 부분합 최대값을 만들어 두는 방식도 가능하다. 노드의 left, right, max, sum 값은 좌측 노드들의 최대부분합, 우측 노드들의 최대부분합, 좌우 전체 최대 부분합 그리고 전체 합을 의미한다. 아래 그림과 같이 left, right, ma...

원문링크 : [알고리즘] 백준 16993