문제 출처 : https://www.acmicpc.net/problem/1912

---

문제 파악

정수 수열이 하나 주어진다.
이 중에서 연속된 몇 개의 수를 골라 합을 구할 때, 만들 수 있는 최댓값을 구하는 문제다.

• 길이 N (1 ≤ N ≤ 100,000)
• 수열의 원소는 음수, 양수 모두 가능
• 연속된 구간의 합 중 최댓값을 출력

예를 들어,

• 수열: 10 -4 3 1 5 6 -35 12 21 -1
• 만들 수 있는 연속 부분 수열 중 최대 합은 12 + 21 = 33

완전 탐색이 가능한가?

• 시작 인덱스 i를 고르고
• 끝 인덱스 j를 고른 뒤
• i ~ j 구간의 합을 전부 구해보고
• 그중 최댓값을 찾는 방법

이렇게 하면 대략:

• i 선택: N 가지
• j 선택: 최대 N 가지
  → 경우의 수: O(N²)
  → 각 구간 합을 매번 계산하면 O(N³) 까지 갈 수도 있음

N이 최대 100,000이라서 N^2 만 하더라도 완전탐색이 불가능하다.

완전탐색은

“모든 구간(i, j)을 다 본다”
라는 관점이었다.

DP로 바꾸려면 관점을 조금 바꿔야 한다.

“각 위치 i에서 끝나는 연속 부분 수열 중, 최댓값은 얼마나 될까?”

이렇게 물어보면, 이전 상태와의 관계를 만들 수 있다.

• dp[i] = i번째 원소에서 끝나는 연속 부분 수열의 최대 합

이렇게 정의하면, dp[i]는 딱 두 가지 선택지 중 하나다.

1. 이전 구간에 이어 붙인다

   • 이전까지의 최대 연속합에 현재 값을 더한다
   • dp[i-1] + a[i]

2. 여기서 새로 시작한다

   • 이전 건 다 버리고, 그냥 현재 값 하나로 시작
   • a[i]

따라서 점화식은 이렇게 나온다.

• dp[i] = max(a[i], dp[i-1] + a[i])

그리고 우리가 진짜로 원하는 값은:

• “어디서 끝나든 상관없이, 전체 수열에서 가능한 최대 연속합”
• 즉, max(dp[0] ~ dp[N-1])

---

해답 및 풀이

import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int,input().split()))

dp =[0]*n
dp[0] = nums[0]

for i in range(1,n):
    prev = dp[i-1]+ nums[i]
    now = nums[i]
    dp[i] = max(prev,now)

print(max(dp))