문제

image.png

풀이

dp[i] = i번째 수로 끝나는 가장 큰 연속합 이라는 점화식을 도출 했다.
i 번째 수에게 가능한 경우를 세야한다.

  1. i-1번째 수의 연속합에 포함되는 경우
    • dp[i-1] + num[i]
  2. 새로운 연속합을 시작하는 경우
    • num[i]

현재 값과 현재값 이전 값 + 현재값을 중 더 큰 값을 dp에 채워 넣으면 된다.
num = {10, -4, 3, 1, 5, 6, -35, 12, 21, -1}
dp = {10,6,9,10,15,21,-14,12,33,32}

코드

#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[100001];
int num[100001];
int main() {
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n; i++) {
        scanf("%d",&num[i]);
    }
    dp[0] = num[0];
    for(int i = 0; i < n; i++) {
        dp[i] = max(num[i],dp[i-1] + num[i]);
    }
    int ans = -2147000000;
    for(int i = 0; i < n; i++) {

        if(dp[i] > ans) ans = dp[i];
    }
    printf("%d",ans);
}