백준1912 연속합

문제

풀이방법

dp[i]=max(dp[i-1]+arr[i],arr[i])

주의할점

배열 초기화 및 배열 넉넉히 세팅

음수가 배열에 들어가니 기준값 잘 설정하기

코드

// bj1912.cpp: 콘솔 응용 프로그램의 진입점을 정의합니다.
//
#include "stdafx.h"
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    long arr[100001] = {0,};
    long dp[100001] = {0,};
    int input;
    long maxval=0;
    cin >> input;
    int i, j, k;

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

    dp[0] = arr[0];
    for (i = 1; i < input; i++) {

        dp[i] = max(dp[i - 1] + arr[i], arr[i]);


    }

    maxval = dp[0];

    for (i = 0; i < input; i++) {
    if (maxval < dp[i])
            maxval = dp[i];
    }

    cout << maxval;
    return 0;
}