문제 출처

1. 문제설명

  • 임의의 수열이 주어진다.
  • 해당 수열에서 연속된 수 중 가장 큰 합을 구하라.



2. 알고리즘 설계

  • DP 문제
  • 가장 앞부터 두 개의 수 씩 더해가면서, 최대 값을 저장한다.
  • 예를 들어, [-1, 2]라면 두 수를 더하는 것보다 2가 더 크기 때문에 2로 저장한다.



3. 로직

  • 점화식
    • DP[i] = max(DP[i - 1] + arr[i], arr[i])
  • 이후 이 값을 현재 저장된 최대값과 비교하면 된다.



4. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int SZ = 100001;
int DP[SZ];
int arr[SZ];

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int ans;

	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	DP[0] = ans = arr[0];
	for (int i = 1; i < n; i++) {
		DP[i] = max(DP[i - 1] + arr[i], arr[i]);
		ans = max(ans, DP[i]);
	}
	
	cout << ans;
	return 0;
}

5. 소감

  • 이런 문제에서 주의해야할 건 특히 자료형이다.
  • 근데 n이 최대 1,000이고, 수열의 개수가 100,000개이므로,
  • int형으로 하였다.