[백준 1912번] 연속합

http://www.acmicpc.net/problem/1912

1912번: 연속합

풀이) 

각 인덱스(i라 가정)마다 뒤로 나아가면서 누적합이 0보다 크면 계속 더해지는 그 순간마다 max(dp[i], sum)을 dp[i]에 갱신해주면 된다.

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, ans = -1001;
    int a[100001], dp[100001];
    
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        dp[i] = a[i];
        int sum = a[i];
        int j = i;
        while (sum + a[++j] > 0 && j <= n)
        {
            sum += a[j];
            dp[i] = max(dp[i], sum);
        }
        ans = max(ans, dp[i]);
    }
    cout << ans;
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!