1912번 : 연속합 - Python

문제

https://www.acmicpc.net/problem/1912

풀이

계속해서 더할지를 결정할때는 더했을때 값이 줄어들면 안된다는 것을 고려해서 더해야 한다. 더해야 하는 값이 음수이면 더했을때 수가 줄어들기 때문에 최대 합이 될 수 없다.

코드

from sys import stdin

input = stdin.readline

n = int(input())

array = list(map(int,input().split()))

dp = [0 for i in range(n)]

dp[0] = array[0]

for i in range(1,n):
    if dp[i-1]>=0:
        dp[i] = array[i]+dp[i-1] 
    else:
        dp[i] = array[i]

print(max(dp))

다른 풀이

A[i]의 수가 최대 값이 될려면 A[i]와 A[i]+A[i-1]중 큰 값을 A[i]에 넣으면 된다.

다른 코드

from sys import stdin

input = stdin.readline

n = int(input())

array = list(map(int,input().split()))

for i in range(1,n) :
    array[i] = max(array[i],array[i]+array[i-1])
    #현재의 수(array[i])와 이전까지의 수(array[i-1])의 합이랑 현재의 수(array[i])중 큰 것을 기억한다.
    
print(max(array))