문제 출처
1. 문제설명
- 임의의 수열이 주어진다.
- 해당 수열에서 연속된 수 중 가장 큰 합을 구하라.
2. 알고리즘 설계
- DP 문제
- 가장 앞부터 두 개의 수 씩 더해가면서, 최대 값을 저장한다.
- 예를 들어,
[-1, 2]
라면 두 수를 더하는 것보다 2가 더 크기 때문에 2로 저장한다.
3. 로직
- 점화식
DP[i] = max(DP[i - 1] + arr[i], arr[i])
- 이후 이 값을 현재 저장된 최대값과 비교하면 된다.
4. 전체 코드
5. 소감
- 이런 문제에서 주의해야할 건 특히 자료형이다.
- 근데 n이 최대 1,000이고, 수열의 개수가 100,000개이므로,
int
형으로 하였다.