[백준] C++ 1912번 연속 합 실버2 - DP

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

해결 방법

• 첫 번째 원소부터 마지막 원소까지 돌면서 가장 큰 합을 구하는 것인데 원소가 10개 주어지면 for문이 10개가 되는 끔찍한 일이 발생한다. 이러한 문제는 대부분이 DP 문제다.

• 저장공간을 생성하고 그 곳에 누적합 중 최고값들을 넣어두면 된다.
  ex) 10 -1 3 15
  dp[0] = 10
  dp[1] = 10 + (-1) 과 (-1) 중 큰 값 = 9
  즉, dp[2] = dp[1] + 3 과 3 중 큰 값 = 12
  dp[3] = dp[2] + 15 와 15 중 큰 값 = 15

  10, -1, 3을 더한 값보다 15가 더 크기 때문에 4번째 저장공간에는 15가 들어가야 한다.
  

풀이

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

int n, maxN;
int dp[100001] = { 0 };
int arr[100001] = { 0 };

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

	maxN = dp[0];
	
	for (int i = 0; i < n; i++) {
		if (dp[i] > maxN) maxN = dp[i];
	}
	
	cout << maxN;
}