문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

www.acmicpc.net/problem/1912

  • 입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

  • 출력

첫째 줄에 답을 출력한다.

최종 코드

연속합 문제는 예전 알고리즘 수업에서 배웠던 문제라서 어렵지 않게 풀었다.

N = int(input())
A = list(map(int, input().split()))
sum = 0
Max = max(A)

for i in range(N):
    if sum + A[i] <= 0:
        sum = 0
    else:
        sum += A[i]
        if sum > Max:
            Max = sum

print(Max)

하지만 이 방법은 C언어로 풀 때 사용했던 방법으로, python을 사용할 때에는 더 간편한 방법이 존재했다.

Enhanced

이전 코드와 아래 코드 모두 B[i] = max(B[i-1]+A[i], A[i]) 라는 점화식을 바탕으로 만들어졌으나 코드가 다르다.

N = int(input())
A = list(map(int, input().split()))
dp = [0]*n
dp[0] = A[0]

for i in range(N):
    dp[i] = max(dp[i-1] + A[i], A[i])

print(max(dp))

참고 사이트