1912번. 연속합

https://www.acmicpc.net/problem/1912

 

 

원트에 풀었지만 다시 생각해보니 생각해볼 만한 점이 있어 포스팅한다.

처음에 생각한 점화식은

이번에 들어가야 할 값 = max(이전까지의 연속합+현재값, 현재값, 현재값+바로 이전 값)

이었다.

왜 현재 값+바로 이전 값을 계산해야 된다고 생각했는지는 잘 모르겠다.

무조건 2개를 선택해서 연속합을 만들어야 한다면, 그렇게 될 것 같다.

 

하지만 문제에서는 1개 이상만 선택하면 된다고 했으니, 점화식은

이번 연속합 = max(바로 이전까지의 연속합+현재값, 현재값) 이 된다.

 

이 뜻은,

현재 값에 연속합을 더하는 것이 낫냐? 아니면 이전 연속합을 더하는게 손해냐? 를 묻는 것이다.

 

예를 들어 주어진 수열이 -1, -1, 55 이라고 생각할 때,

연속합+현재값은 53이고 현재 값은 55이므로 최대 연속합은 55이다.

이전 연속합들을 데리고 갈지, 아니면 더하면 오히려 손해이므로 버리고 갈 지를 결정한다고 생각하면 된다.

 

주석친 곳을 보면 

maxSum = max(seq[now]+subsum[now-1], seq[now]) 라고 되어 있는데, 이것이 볼드처리한 점화식과 같다.

seq는 주어진 수열, subsum은 연속합을 저장한 배열이다.

하지만 이 max 를 보면, seq[now]가 양쪽에 공통되어 있다는 사실을 알 수 있는데.

그렇다면 max(subsum[now-1], 0)이 된다.

이것을 풀어서 생각해보면 

이전까지의 연속합이 0을 넘느냐? 이다.

이전까지의 연속합이 0을 넘으면, 현재 값이 양수든 음수든 무조건 더하는게 이득이므로 데리고 간다. 라는 뜻이다.

그래서 본문과 같이 if문으로 바꿔봤더니 속도가 더 빨라졌다.

import sys
N = int(sys.stdin.readline())
seq = list(map(int, sys.stdin.readline().split())) # 주어진 수열
subsum = [seq[0]]  # 연속합을 저장할 리스트

for now in range(1, N):
    # 연속 합에 현재 값을 더하는 게 낫냐? OR 현재 값에서 다시 시작하는 게 낫냐?

    #maxSum = max(seq[now]+subsum[now-1], seq[now])
    #subsum.append(maxSum)

    if subsum[now-1] > 0:
        subsum.append(seq[now] + subsum[now-1])
    else:
        subsum.append(seq[now])


print(max(subsum))