클래식 dp - 최대 하위 섹션 및

51Nod-1049

N개의 정수로 구성된 서열 a11, a22, a33,..., ann, 이 서열은 aii+ai+1i+1+...+ajj의 연속 자단과 최대 값을 구합니다.주어진 정수가 모두 음수일 때와 0이다.예를 들어 -2,11,-4,13,-5,-2와 가장 큰 자단은 11,-4,13이다.합은 20이다.Input 1행: 정수 시퀀스 길이 N(2 <= N <= 50000) 2- N + 1행: N개의 정수(-10^9 <= Aii <= 10^9) Output 출력 최대 하위 세그먼트 합.Sample Input 6 -2 11 -4 13 -5 -2 Sample Output 20
sum로 현재 하위 세그먼트와 0보다 작으면 sum=0,ans로 가장 큰 하위 세그먼트를 저장하면 됩니다. 롱롱 롱을 주의하세요.

#include
#include
using namespace std;
typedef long long ll;
int a[50050];
int main()
{
    ll n,sum=0,ans=0,i;
    scanf("%d",&n);
    for(i = 1;i <= n; i++)
        scanf("%d",&a[i]);
    for(i = 1;i <= n; i++)
    {
        sum += a[i];
        if(sum <= 0)
            sum = 0;
        else
            ans = max(ans,sum);
    }
    printf("%lld
",ans);
    return 0;
}