[백준] 1912번(python 파이썬)

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

 

연속된 숫자를 몇개 선택해서 더했을때 가장 큰 합을 구하는 것이다.

이는 양수는 계속 더해주고 음수일때 선택을 해야한다. 연속해서 더할 것인지 더하지 않을 것인지 정해야한다.

만약 숫자가

6
-5 1 2 3 -4 5

이렇게 있다면

1 2 3 은 더해서 6을 만든다.

이때 연속된 수로 -4가 나오게 되는데 계속 더해줄 것인지 빼고 다음 숫자부터 다시 시작할 것인지...

 

그렇다면 어떻게 정할까?

음수를 더했을때 보다 해당 음수 보다 클 경우 더해주면 된다.

1 + 2 + 3 = 6

(6 + -4  = 2 ) > -4 이기 때문에 계속 더해준다.

 

이런식으로 하면

1 2 3 -4 5 를 선택했을때 제일 큰 수 7이 나온다.

 

만약 음수를 기준으로 더하고 말지를 정한다면 ( 처음에 생각한 방법)

1 2 3 를 선택한 6이 제일 큰 값이 나오기 때문에 잘못된 방법이다.

 

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

dp = [0] * len(s)

for i in range(len(s)):
    if i == 0:
        dp[i] = s[i]
    if s[i-1] >= 0:
        dp[i] = s[i] + dp[i-1]
    else:
        if s[i] < s[i] + dp[i-1]:
            dp[i] = s[i] + dp[i-1]
        else:
            dp[i] = s[i]

print(max(dp))