[백준, python] 1912번 - 연속합
백준 문제풀이 시작
문제
n개의 정수로 이루어진 임의의 수열이 주어진다.
우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
입력
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
첫째 줄에 답을 출력한다.
풀이
풀이 확인하기
입력받는 리스트와 memoization을 위한 리스트를 만들어 주고, memoization용 리스트의 첫번째에 입력받은 리스트의 첫번째 값을 담는다. 이후 나머지는 memoization 리스트의 현재보다 한칸 전 값에 현재 값을 더한 값과 현재 값을 비교 해 더 큰 값을 담는다. 이후 memoization 리스트에서 가장 큰 값을 출력한다.
num = int(input())
arr = list(map(int, input().split(" ")))
mem = [0]*num
mem[0] = arr[0]
for i in range(1, num):
mem[i] = max(arr[i], mem[i-1] + arr[i])
print(max(mem))