백준 1912 파이썬 python : 연속합 @@황소처럼 우직하게@@ 잘생각해보자

수열이 한개라면 그 수열이 최대값이다.

그 수열 한개에 한개가 새로 오른쪽으로 들어온다.

그러면 연속합의 최대는 그 첫 번째 값 혼자거나,

두번째값 혼자거나, 첫번째 값이 들어간 연속최대값과 두번째값을 합친 값이거나

=> max(dp[1], dp[2]) 인데 

dp[2] = max(lst[2], dp[1] + lst[2])

-- (편의상 설명은 첫번째 == 1, 두번째 == 2 로 하겠다. 코드 구현은 인덱스로 했다.)

세번째 수가 오른쪽으로 새로 들어온다.

그러면 최대는

첫 번째 값이 포함된 연속된 최대값이거나,

두 번째 값이 포함된 연속된 최대값이거나,

세 번째 값 혼자거나, 두 번째 값이 포함된 연속된 최대값 + 세 번째 값이거나

=> max(dp[1], dp[2], dp[3]) 인데

dp[3] = max(lst[3], dp[2])

하튼

수가 많아지면 -이든 +이든

선택해서 취하면 된다.

--

좀더쉽게 설명하면

--

계속 +를 먹다가 - 를 만났다고 치자

- 직전 인덱스에 모든 +를 합친 값이 들어가있다.

-인덱스 입장에서는 모든 수들을 합친 값이 최대값이다.

이 때 새로운 수 + 가 들어온다고 하자

- 인덱스 값이 음수가 아니라면

- 값까지 연속되는게 이득이다. 새로운 인덱스 입장에서는

결국               (이런상황 : 3 7 5 3 -17 1)

이 알고리즘은 단순히 1개씩 더해나가는걸로 보이지만

-가 가운데 낑겨있는 것도 충분히 고려하고 있는 알고리즘이다.

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

dp = [x for x in lst]

for i in range(1, n):
    dp[i] = max(dp[i], dp[i - 1] + lst[i])

print(max(dp))