1912 연속합

연속합 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	43173	11732	8089	26.895%

문제

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

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

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

작년에 C++로 열심히 풀다가 화나가서 답을 찾아본 기억이있다.

오랜만에 완전탐색 공부하려고 이 문제를 들여다 봤는데, 

전혀 기억이 안나서 초심을 가지고 꾸역꾸역 다시풀어 보았다.

역시나 이번 시도도 순탄하지는 않았다. 결국엔 내가 C로 옛날에 짠 소스를 보았다.

그런데 왠걸? 내가 거의다 풀었었다. 조금만 머리를 굴렸으면 됬었는데

그걸 못참아서 힌트를 보고 ^&#$*&ㅃ#$^ 를 외쳤다.

아아 조금만 더 생각할걸..... 옛날의 패배를 설욕할 기회였는데 

그래도 긍정적으로 생각하자면 마지막 결정적인 생각을 못해서 틀렸다는점.

접근방법은 아주 좋았던점을 꼽아 정신승리를 해야겠다.

풀이를 해보자면

너무 빠르게 써서 악필이긴하나,

요약하자면, 각 len의 최대값은 그전 len최대값 + 마지막값 과 마지막값을 비교만하면 구할 수 있고,

그 각 len의 최대값들로 이루어진 배열의 최대값을 구하면 끝.

아래는 소스코드입니다.

import sys

sys.stdin.readline()

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

arr_list = []

for i,v in enumerate(arr):

arr_list.append(v) if(i is 0) else arr_list.append( v if(v>=v+arr_list[-1]) else v+arr_list[-1] )

print(max( arr_list ) )