[Silver 2] 1912번 연속합

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

1912번: 연속합

 

이 문제는 DP를 통해 해결할 수 있다.

 

알고리즘은 다음과 같다.

• 주어진 입력을 배열에 담는다.
• dp[0]을 배열의 0번째 요소로 초기화한다. 이때 maxNum도 배열의 0번째 요소로 초기화한다.
• 배열을 순회하며 dp에 값을 누적시키고, 누적합과 배열의 i번째 요소 중 큰 값을 dp에 저장한다.
  • 이는 누적합을 구할 때 자를 부분을 선정하는 것이다.
  • dp는 3, -1, 3, 7, 3, 9, 14, ...으로 변화한다.
  • 이 값은 2+1, 2+1-4, 3, 3+4, 3+4-4, 3+4-4+6, 3+4-4+6+5로 값이 잘리게 된다.

 

#include <iostream>
#include <cmath>
using namespace std;

int N, maxNum;
int dp[100001];
int arr[100001];

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	dp[0] = arr[0];
	maxNum = arr[0];
	
	for (int i = 1; i < N; i++) {
		dp[i] = max(dp[i - 1] + arr[i], arr[i]);
		maxNum = max(dp[i], maxNum);
	}
	cout << maxNum << '\n';
}