백준 13398번 연속합 2

연속합 1에서 진화됐다.

 

일단 기본적으로 연속합1 처럼 계산하는데 음수부분을 하나씩 빼보면서 완전탐색처러 풀어도 될거같고

아니면 음수등장이전값이 가장큰데 음수보다 작은값인 애들을 합치는것도 괜찮을듯 하다.

두번째 방법이 맞는듯 하다. 가장큰거랑 두번째로 큰거 구해서 더하면 되는거잖아

 

import sys

n=int(sys.stdin.readline().rstrip())
arr=list(map(int,sys.stdin.readline().rstrip().split()))

v=[[0]*2 for _ in range(n)]
if arr[0]>=0:
    v[0][0]=arr[0]
    v[0][1]=0
else:
    v[0][0]=0
    v[0][1]=0
for i in range(1,n):
    sum=0
    if v[i-1][0]+arr[i]<=0:
        if arr[i]>=0:
            v[i][0]=arr[i]
        else:
            v[i][0]=0
            v[i][1]=v[i-1][0]
    else:
        if arr[i]>=0:
            v[i][0]=v[i-1][0]+arr[i]
        else:
            v[i][0]=v[i-1][0]+arr[i]
            v[i][1]=v[i-1][0]
    
    if v[i-1][1]!=0:
        v[i][1]=max(v[i][1],v[i-1][1]+arr[i])
zero_check=True
for i in range(n):
    if v[i][0]>0:
        zero_check=False
        break
if zero_check:
    result=arr[0]
    for i in range(n):
        result=max(arr[i],result)
    print(result)

else:
    result=v[0][0]
    for i in range(n):
        for j in range(2):
            result=max(result,v[i][j])
    print(result)

이렇게 작성했다.

 

근데 이거 틀리면 진짜 많이 머리 아플 것 같다.

진짜 생각할게 많아서 힘들었다.

 

이궈궈든!!!