더블릿 문제풀이(최대 구간 구하기)

프로그램 명: minterval

제한시간: 1 초

서로 다른 정수의 값이 일렬로 주어졌을 때, 가장 큰 합을 가지는 부분 구간을 구하시오. 여기서 부분구간이란 연속된 구간을 의미한다.

예를 들어, 다음과 같은 값이 주어지면,

-2 9 2 -6 7 -7 5

최대 구간은 [9 2 -6 7]이며, 합은 12 이다.

입력

입력의 끝은 0 으로 인식한다.

수의 개수는 2,000 개를 넘지 않는다.

출력

최대 구간의 합을 출력한다.

입출력 예

입력

-2
9
2
-6
7
-7
5
0

출력 

12

출처 | dovelet



대표적인 dynamic programming이라고 볼 수 있겠습니다..
이걸 모든 경우로 구하려고하면 엄청나게 시간소모가 될 꺼 같지만
적당한 점화식을 구해서 구해보면 적은 시간에 답을 뽑아낼 수 있겠죠......
dynamic programming이란 일부분의 답을 구해 하나씩 더해가 최종 답을 구하는(?) 그런 
프로그래밍 기법이라고 볼 수 있습니다.
소스코드를 보시면 더 이해가 빠르실거에요.

main.cpp
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <string>
#include <cmath>

using namespace std;

int main()
{
   int a[10000], dp[10000]={0};
   int result, i, n;
   for(i=0; ; i++){
           cin >> a[i];
           if(a[i]==0)
                break;
   }
   n = i;
   for( i = 0 ; i < n ; i++)
dp[i] = a[i] > a[i] + dp[i-1] ? a[i] : a[i] + dp[i-1];
   result = dp[0];
   for( i = 1 ; i <n ; i++)
      if ( result < dp[i] ) result = dp[i];
   cout << result << endl;
}