boj 1912 : 연속합

문제 주소: https://www.acmicpc.net/problem/xxx

난이도: silver 2

1.문제설명

• n개의 숫자로 구성된 수열이 주어졌을 때
• 이중 연속된수(1개 이상 선택)의 합의 최대값은?

2.문제해결 아이디어.

• 수열을 리스트로 받는다 (numbers로 받음)
• 이와 대응시킬 cache table을 만든다
• cache[i] = i번째 숫자까지 연속된 최대합

3.문제접근법

• 최대화를 시키는 문제이고, 주어지는 원소의 최소값은 -999이므로 아래와 같이 설정한다.

cache = [-1000] * (N)
cache[0] = numbers[0]

• 1번째부터 N번째까지 다음과 같은 점화식으로 업데이트 시켜주면 된다.

    cache[i] = max(numbers[i], numbers[i] + cache[i-1])

• i번째 숫자까지 연속된 최대합 = i번째 숫자, i번째 숫자 + i-1번째 숫자까지 연속된 최대합 중 더 큰값이다.

4.특별히 참고할 사항

-메모이제이션 테이블의 i번째 원소가 어떤 의미를 가지는지 잘 정의하자

5.코드구현

N = int(input())
numbers = list(map(int, input().split()))
cache = [-1000] * (N)
cache[0] = numbers[0]
for i in range(1,N):
    #cache[i] = i번째 숫자까지 연속된 최대합
    cache[i] = max(numbers[i], numbers[i] + cache[i-1])
print(max(cache))