1912 연속합 (재시도 -0)

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

 

키워드 :

연속되게 더할 수가 더하지 않을때보다 크면 더하고 아니면 break하는걸 생각했다.

 

부족했던것: 일단 조건을 좀 잘못설정했다. 나는 dp[i]를 i번째까지 연속합의 최대값으로 정했을 때,

dp[i-1]+arr[i] 과 dp[i-1]을 비교했다. 왜나면 저렇게 비교해서 첫번째가 더 작으면 멈추고 2중for문으로

다음 번호로 넘어가도록 했다. 

그런데 이렇게 했을 때 dp[]값들이 중복되면서 엉망으로 된것 같다.

 

그리고 2가지를  계속 실수하는데 하나는 dp테이블 시작번호랑 arr같은 수열 테이블 시작번호랑 다르게할 때 좀 헷갈리는거랑 dp테이블 크기 처음에 정하는거다. 

이걸 좀 생각해야 되는게 dp테이블번호를 1부터 쓸거면 초기화도 n+1로 해줘야되고 0부터 쓸거면 n까지만 초기화 해줘야 된다.

 

풀이 알고리즘 방법은 dp[i-1]+arr[i] 와 arr[i]중 max값을 저장시키는 거였다. 내가 생각을 못했던게 양수끼리만 더하는 수보다 이전부터 양수음수 전부 더한 수가 당연히 더 클수 있다는 점이었다.

 

 

#1 n입력받기
n=int(input())
arr=list(map(int,input().split()))
dp=[0]*n
dp[0]=arr[0]

'''실수한 부분
for i in range(2,n+1):
  for j in range(i+1,n+1):
    if dp[i-1]+arr[i-1]>dp[i-1]:        비교도 잘못됐고, 내부 for문이 한번 돌아서 생긴 dp값에 다음for문이 이상하게 영향을 받게 되서 잘못짰다.
      dp[i]=dp[i-1]+arr[i-1]
    else:
      dp[i]=dp[i-1]
break
'''

#dp이전값에 현재 i번째의 배열수를 더한것(이전까지의 모든수의 합)이 i번째 배열수보다 크면 그값으로 바꾼다.
for i in range(1,n):
    dp[i]= max(dp[i-1]+arr[i],arr[i])
print(max(dp))