[Java] 연속 펄스 부분 수열의 합

문제 접근법 1(완전 탐색) 문제가 간단해 금방 풀수 있을 것이라고 생각했지만, 생각보다 문제를 푸는데 시간을 많이 소요했습니다. 첫번째 접근법은 완전 탐색이었습니다. 사실 이것으로는 풀리지 않을것이라 예상은 하고 있었지만, 금방 구현할 수 있기에 시도해보았습니다. 주어진 문제는 수열에 펄스를 준 이후 연속된 수열의 최대값을 찾는 것입니다. [2, 3, -6, 1, 3, -1, 2, 4] 문제를 풀면서 한가지 알게된 것이 있습니다. 위와 같이 배열이 있을때, 펄스 수열을 곱해보겠습니다. 펄스 수열 1 [-2, 3, 6, 1, -3, -1, -2, 4] 최대 값: 3 + 6 + 1 = 10 최소 값: -6 펄스 수열 2 [2, -3, -6, -1, 3, 1, 2, -4] 최대 값: 3 + 1 + 2 = 6 최소 값: -3 -6 -1= -10 즉, "어떤 펄스 수열을 곱하듯 최대/최소 크기는 같다"는 것입니다. 따라서, 첫 번째 풀이방법은 모든 구간의 합을 구하면서 동시에 그 값이 음수...

원문링크 : [Java] 연속 펄스 부분 수열의 합