백준 #1912 <연속합> 파이썬

난이도 : 실버2
소요시간 :  27m
사용한 풀이법 : DP

---

풀이 과정

1. 입력받은 문자열을 정수형 리스트 arr[]로 변환
2. dp[]에는 해당 인덱스에서 가질 수 있는 최대값을 넣는다
3. dp[i-1]+arr[i]가 음수일 경우 최대값 생성에 방해가 되므로 해당 dp값은 0으로 초기화
4. 원래는 여기서 풀이를 끝낼라했는데 모두 음수일 경우를 고려안하게 생각나서 dp첫번째 조건문 뒤에 arr값을 dp값으로 초기화 해주는 코드 추가 ⇒ 내가 생각해도 좀 후진 코드..ㅎ
5. 원래는 max(dp)를 하려했으나 위 코드 추가되면서 max(arr)로 변경

다른 풀이

1. 입력받은 문자열을 정수형 리스트 arr[]로 변환
2. 현재합과 최대합 연산용 변수 선언
3. arr을 돌면서 해당 인덱스와 해당 인덱스에 현재합을 더한 것중 max를 현재합에 대입
4. 다시 max연산을 통해 최대합 도출

작성 코드

n=int(input())
dp=[0]*n
arr = list(map(int,input().split()))
    
dp[0] = arr[0]

for i in range(1,n):
    if dp[i-1] + arr[i] > 0:
        dp[i] = dp[i-1]+arr[i]
        arr[i] = dp[i-1]+arr[i]
    else :
        dp[i] = 0

print(max(arr))

#2차 코드

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

max_sum = arr[0]
current_sum = arr[0]

for i in range(1, n):
    current_sum = max(arr[i], current_sum + arr[i])
    max_sum = max(max_sum, current_sum)

print(max_sum)