[프로그래머스] 연속 펄스 부분 수열의 합 / Prefix Sum, 구간 합
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/161988# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 풀이 전략 주어진 sequence 수열에 [1, -1, 1, -1, ...]이 곱해진 수열과 [-1, 1, -1, 1 ...]이 곱해진 수열을 만든다. 두 수열 에서 특정 구간을 더했을 때 그 합이 제일 큰 것을 구하면 답이다. 이 아이디어를 구현할 때 sequence의 길이가 50,000까지 가능하다는 점에 유의해야 한다. 시간 복잡도를 고려하여 O(n) 시간에 정답을 구..