연습문제
어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 모두 곱한 뒤 그 합이 가장 큰 값을 갖는 수열을 찾는 문제입니다.
여기서 펄스 수열은 [1, -1, 1, -1 ...] 처럼 1과 -1을 왔다갔다 하는 수열이라고 합니다.
접근법
어쨌든 우리는 주어진 수열과 펄스 수열을 곱해야 하기 때문에 처음에 미리 곱해주고 시작합시다.
펄스 수열은 1 or -1 둘 중에 한개로 시작하니까 종류도 두 가지가 있겠죠?
주어진 수열도 똑같이 둘로 만들어 줍시다.
sequence2 = sequence[:]
purse = 1
for i in range(len(sequence)):
sequence[i] *= purse
purse *= -1
sequence2[i] *= purse
이제 만들어진 수열을 탐구해 보도록 합시다.
수열의 값은 랜덤이기 때문에 [~양수로 이루어진 부분수열~]과 [~음수로 이루어진 부분수열~] 두 종류로 이루어져 있을 것입니다. 여기서 중요하게 생각할 점은 양수로 이루어진 부분수열의 총 합과 음수로 이루어진 부분수열을 합에 포함할 것 인가? 이 두가지가 되겠습니다.
양수로 이루어진 부분 수열이야 당연히 고려해야 하는것이 맞지만, 음수로 이루어진 부분 수열은 제외해야 맞는것이 아니야?? 합에 포함하면 값이 줄어들텐데.. 라고 생각하실 수도 있습니다. 저도 그랬어요
하지만 우리가 음수로 이루어진 부분 수열을 합에 포함시키는 이유는 바로 그 부분 수열 다음에 올 <양수로 이루어진 부분 수열>을 합에 추가시키기 위함입니다.
예시를 들어볼게요.
[-2, 3, 6, 1, -3, -1, -2, 4]
예시에서 주어진 수열에 제가 펄스 수열을 곱한 것입니다. 이 수열은 [-2] [3, 6, 1] [-3, -1, -2] [4] 이렇게 총 네 부분으로 나누어 볼 수 있겠습니다.
[-2]는 처음에 오기 때문에 합에 추가해봤자 아무런 의미가 없습니다. 제외시키고 [3, 6, 1] 부터 보는걸로 합시다. 양수로 이루어진 부분 수열이니 당연히 총 합에 추가해 주는겁니다. 3 + 6 + 1 = 10이 되었습니다.
다음으로 음수로 이루어진 수열, [-3, -1, -2] 입니다. 이 수열을 고려하는 이유는 바로 다음 수열인 [4]를 합에 넣기 위해 고려한다고 했죠? 해봅시다. -3 + -1 + -2 = -6 인데 이 수열을 추가하면서 까지 [4]를 합에 넣으면 될까요? -6 + 4 = -2 이므로 결국 손해입니다. 따라서 정답은 3 6 1만을 포함한 10이 되는겁니다.
그런데 만약 마지막에 온 수열이 [4]가 아니라 [100]이라면? 당연히 [-3, -1, -2]를 추가해서라도 수열을 연결시켜야겠죠. -6보다 월등히 큰 값이니까요. 말 그대로 살을 주고 뼈를 취하는 느낌입니다.
코드로는 어떻게 구현할까요?
수열은 왼쪽(인덱스 0) 부터 순차적으로 탐색한다고 생각합니다. 우리가 음의 수열을 합에 집어넣는 조건은 음의 부분 수열의 총 합의 절댓값보다 양의 부분 수열의 총 합의 절댓값이 더 큰 경우입니다. 그 말인 즉, 수열의 원소를 차례차례 더해 나갔을 때 총 합이 음수가 되는 지점이 있다면, 그 지점을 포함한 음의 부분 수열의 합이 이전의 양의 부분 수열의 합보다 절댓값이 크다는 것이 됩니다.
우리는 수열의 어느 한 구간만을 찾아야 하기 때문에 중간중간 부분수열 합의 최댓값을 저장해줘야 할 필요가 있습니다. tmp라는 변수를 만들어 이 변수에 원소를 하나씩 더해주고, tmp의 최댓값은 max_sum 이라는 변수에 저장해 보겠습니다.
max_sum = 0
tmp = 0
for s in sequence:
tmp += s
if tmp < 0:
tmp = 0
max_sum = max(max_sum, tmp)
tmp의 값이 음수가 된다는 것은, 우리가 음의 부분 수열을 지나는 중이고, 이 음의 부분 수열이 양의 부분 수열의 크기를 넘어섰다 라고 미루어 볼 수 있습니다. 고려할 필요가 없는 수열이라는 뜻입니다. tmp가 음수가 된다면 다시 0으로 만들어 줍시다. 지금의 음의 부분 수열을 무시함과 동시에 바로 다음에 올 양의 부분 수열을 0부터 고려할 수 있게 됩니다.
필요없는 음의 부분 수열 이전에 있던 양의 부분 수열의 합은 고스란히 max_sum에 저장되어 있습니다. 음의 부분 수열에 들어서는 순간 max_sum은 갱신되지 않을 테니까요.
혹은 예제처럼, tmp가 음수가 되지 않을 수도 있습니다. 3 + 6 + 1 - 3 - 1 - 2 = 4로 음수가 되지 않습니다. 그럼에도 [-3, -1, -2]는 [4]보다 합의 절댓값이 크므로 마지막 4를 더해도 8, [3, 6, 1]만 고려한 10보다는 값이 작기 때문에 max_sum이 갱신되지 않습니다.
그런데 펄스 수열은 종류가 총 두 가지였죠? 처음에 만들어놓았던 두 번째 수열도 사용해서 max_sum 값을 구해줍니다. 첫 번째 수열에서 두 번째 수열로 넘어갈 땐 tmp의 값을 0으로 초기화 해주는걸 잊지 말아야 합니다.
tmp = 0
for s in sequence2:
tmp += s
if tmp < 0:
tmp = 0
max_sum = max(max_sum, tmp)
그렇게 하고 나면 총 세번을 순차 탐색하는 방법이 완성됩니다.
코드
def solution(sequence):
answer = 0
sequence2 = sequence[:]
purse = 1
for i in range(len(sequence)):
sequence[i] *= purse
purse *= -1
sequence2[i] *= purse
max_sum = 0
tmp = 0
for s in sequence:
tmp += s
if tmp < 0:
tmp = 0
max_sum = max(max_sum, tmp)
tmp = 0
for s in sequence2:
tmp += s
if tmp < 0:
tmp = 0
max_sum = max(max_sum, tmp)
answer = max_sum
return answer