문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

풀이

10,-4,3,1,5 까지의 수열에서 연속합을 구해준다고 하였을 때, 모든 경우의 수를 고려하면 다음과 같다.

선택 영역_357

그래서 최종 10 vs 6 vs -4 vs … 15개의 숫자를 비교해주는 노가다 방식이다.

그런데 예를 들어 세 번째 경우를 보면, 어차피 3을 다 더해준 후 비교할꺼라면 6 이 -4 보다 컸으므로 3을 똑같이 더한 9가 -1 보다 큰 것도 당연하다. 따라서 연노란색 음영표시된 부분은 사실 할 필요가 없는 불필요한 연산이 된다.

선택 영역_358

정리해보면 이전 번째에서의 최대값에 현재 번째 숫자를 더한 값과 현재 번째 숫자 를 각 번째 dp 에 저장해준 후, 전체 dp 에서의 최대값을 구하면 된다.

코드

import sys
input=sys.stdin.readline

class FindMax:
    def read(self):
        self.n=int(input())
        self.numb=list(map(int,input().split()))
    
    def solve(self):
        self.dp=[]
        for i in range(self.n):
            cur=[]
            if i==0:
                cur.append(self.numb[0])
                self.dp.append(cur)
            else:
                cur.append(max(self.dp[i-1])+self.numb[i])
                cur.append(self.numb[i])
                self.dp.append(cur)
        ans=float("-inf")
        for cand in self.dp:
            cur_cand=max(cand)
            if cur_cand>ans:
                ans=cur_cand
        print(ans)
       
        
fm=FindMax()
fm.read()
fm.solve()