백준 알고리즘 1912번: 연속합(Python)

https://www.acmicpc.net/problem/1912

1912번: 연속합

---

문제 해결을 위한 과정

이 문제의 경우 연속적으로 순자를 선택한 후 그 합이 최대가 되도록 하면 해결할 수 있는 dp 문제입니다. 따로 dp 리스트를 만들기보다 입력받은 리스트를 그대로 활용하면 보다 간단하게 해결할 수 있는 문제였습니다. 먼저 예시를 통해 알아봅시다.

 

0번째 인덱스까지의 최대의 합은 0번째 인덱스 그대로입니다.

10

-4

3

1

5

6

-35

12

21

-1

 

1번째 인덱스까지의 최대의 합은 1번째 인덱스 그대로가 아닌 0번째 + 1번째입니다.

10

6

3

1

5

6

-35

12

21

-1

 

2번째 인덱스까지의 최대의 합은 2번째 인덱스 그대로가 아닌 0번째 + 1번째 + 2번째입니다.

10

6

9

1

5

6

-35

12

21

-1

 

위와 같은 방식으로 6번째 인덱스 까지는 인덱스 그대로가 아닌 합으로 이루어집니다. 이는 아래의 그림과 같습니다.

10

6

9

10

15

21

-14

12

21

-1

 

다만, 7번째 인덱스까지의 최대의 합은 0번째부터 7번째까지의 합이 아닌 7번째 인덱스 그 자체입니다. 따라서 7번째 인덱스는 그대로 유지됩니다.

10

6

9

10

15

21

-14

12

21

-1

 

8번째 인덱스까지의 최대의 합은 8번째 그대로가 아닌 7번째 + 8번째입니다.

10

6

9

10

15

21

-14

12

33

-1

 

9번째 인덱스까지의 최대의 합은 9번째 그대로가 아닌 7번째 + 8번째 + 9번째입니다. 위의 표를 기반으로 점화식을 작성하면 다음과 같습니다.

 

data[i] = max(data[i], data[i-1] + data[i])

이를 소스코드로 표현하면 다음과 같습니다.

---

소스코드

n = int(input())
data = list(map(int, input().split()))
 
for i in range(1, n):
  data[i] = max(data[i], data[i] + data[i-1])
  
print(max(data))