[백준 1912번] 파이썬 - 연속합

백준 1912-연속합

시간 제한 1초, 메모리 제한 128MB

# 조건

• n개의 정수로 이루어진 임의의 수열이 주어진다.
• 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다.
  • 단, 수는 한 개 이상 선택해야 한다.
  • 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

# 접근 방법

• 누적 합과 비슷하게 풀면 되지만 음수가 존재한다.
• 따라서 DP를 이용하여 풀어준다.
• NUMS 를 입력받은 후 최소 1개의 수를 선택해야 하므로 0번 인덱스를 선택한 것을 기본값으로 한다.
• 1부터 N까지 순회하는데
  • nums[i] = max(nums[i], nums[i-1] + nums[i]) 를 통하여 연속되는 수의 합이 최대가 되는 것을 갱신해오며 풀어주면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N = int(input())  
nums = [*map(int, input().split())]  

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

print(max(nums))