[백준/1912] 연속합(Python3)

문제 링크: https://www.acmicpc.net/problem/1912

문제 접근

해당 문제는 원 배열(arr)과 최대 값을 저장하는 배열(sum_arr)을 두고, 각 자리마다 최대 값을 갱신하는 문제이다.

배열	0	1	2	3	4	5	6	7	8	9
arr	10	-4	3	1	5	6	-35	12	21	-1
sum_arr	10	6	9	10	15	21	-14	12	33	32

위의 표를 보면, sum_arr[i-1]+arr[i]와 arr[i] 중에 더 큰 것을 선택하여 sum_arr[i]를 갱신하는 것을 볼 수 있다. 이것만 알면 해결 ssap가능이다.

소스 코드

from typing import List


def get_input() -> List[int]:
  input()

  arr: List[int] = [int(i) for i in input().split(" ")]
  return arr

  
def caculate(arr: List[int]) -> int:
  length: int = len(arr)
  max_value: int = arr[0]

  sum_arr: List[int] = [0] * length
  sum_arr[0] = arr[0]

  for i in range(1, length):
    sum_arr[i] = max(sum_arr[i - 1] + arr[i], arr[i])
    max_value = max(max_value, sum_arr[i])
  
  return max_value
  

print(caculate(get_input()))