[동적계획법, 난이도 중상] 백준 1912번 연속합

연속된 자릿값을 더해서 나올 수 있는 최댓값을 구하는 문제이다.

이 문제는 아주 특수한 경우 하나를 처리해줘야 한다.

- 양수가 하나도 입력 되지 않았을 경우

이 경우에는 입력 값들의 최댓값이 정답이 된다.

 

이제, 나머지의 경우에 대해 DP를 수행해보자.

위 사진은 내 접근법에 대한 DP표이다.

 

먼저, 첫 번째 dp인덱스의 값은 첫 번째 입력값과 동일하다. 

그리고 이후의 dp인덱스에 대해서는 다음과 같은 식을 이용했다.

d[i]=max(0, d[i-1]+e[i]);

 

#include <iostream>
#include <algorithm>
using namespace std;
int e[100001];
int d[100001];
int n, ans;
int maxi=-1000;

int main() {
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>e[i];
		if(e[i]>maxi)maxi=e[i];
	}	
	d[1]=e[1];
	for(int i=2;i<=n;i++)d[i]=max(0, d[i-1]+e[i]);
	sort(d,d+n+1,greater<int>());
	if(maxi<=0) cout<<maxi; //양수가 하나도 입력 되지 않았을 경우
	else cout<<d[0];
}

 

 

+) 2021-10-03 백준 숏코딩 상위 1.9% 파이썬

n=int(input())
e=list(map(int,input().split()))
d=[e[0]]
for i in range(1,n):d.append(max(0,d[i-1]+e[i]))
if max(e)<=0:print(max(e))
else:print(max(d))