[C++] 백준 1912번 : 연속합

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

문제

수열이 있을 때, 부분 수열의 합의 최댓값을 구하기

• 점화식

1.  a[i] = max(a[i-1] + a[i], a[i])
2.  max_val = max(a[i], max_val)

 

첫번째 식은, (1) 이전 값들을 반영한 값과 (2) 반영하지 않은 값을 비교해서 더 큰 값을 저장하도록 하기 위함이다.

 

두번째 식은, (1) 현재 차례에서 반영된 값과, (2) 전역 최댓값을 비교해서 더 큰 값으로 갱신하기 위함이다.

 

처음에는 스택으로 푸는 건가,, LIS(최장 증가 수열)의 응용인가..

싶었는데,, 그냥 DP다.. 점화식을 잘 찾아보자..

 

 

풀이

#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    vector<int> nums(n);
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }

    int max_val = nums[0];

    for (int i = 1; i < n; i++)
    {
        nums[i] = max(nums[i - 1] + nums[i], nums[i]);
        max_val = max(max_val, nums[i]);
    }
    cout << max_val;
}