(1912)(DP) 백준 연속합

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

풀이

---

연속된 수열이 있을때 이 중 연속된 몇개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 문제이다.

dp배열(기록해두는 배열)를 이용해서 수열 arr[1]부터 마지막 배열인 arr[n]까지 연산할 것이다.

먼저 arr[1]의 값을 dp[1]에 넣고 

if(dp[n-1] + arr[n] > arr[n]) 의 조건을 준다.

이전 dp(즉, arr[1]부터 arr[n-1] 까지의 합)가 0보다 큰 수라면 다음 배열 arr[n]도 더해서 다음 dp[n]에 저장하도록 한다.

하지만 만약 dp[n-1]이 0이거나 음수라면 과감하게 버려주고 dp[n]에 arr[n]만 넣어준다.

----->>

if(dp[n-1] + arr[n] > arr[n]) dp[n] = dp[n-1] + arr[n];

else dp[n] = arr[n];

위와 같은 식으로 알고리즘을 짜면 그때그때 수열의 합값을 dp에 기록하고 이전 dp가 0으로 접어들게 되면 이전 앞에서 부터 더해줬던 값들은 더할 의미가 사라지기 때문에 꼬리를 자르는 것처럼 버려준다. 그 대신 arr[n]값을 dp[n]에 넣어준다.(이 값이 dp[n]이 가질 수 있는 최대값) 이런식으로 배열 마지막까지 수행하게 되면 dp배열이 만들어 지게 되고

그리고 int Max; 를 만들어서 

Max = dp[1]

for(int i=1; i<N; i++){

if(Max < dp[i]) Max = dp[i];

}

를 해주면 된다.

#include <stdio.h>
 
int main() {
    int arr[100001] = { 0 };
    int dp[100001] = { 0 };
    int N;
    int Max;
 
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    for (int i = 1; i <= N; i++) {
        if (arr[i] < dp[i - 1] + arr[i]) {
            dp[i] = dp[i - 1] + arr[i];
        }
        else {
            dp[i] = arr[i];
        }
    }
    Max = dp[1];
    
    for (int i = 2; i <= N; i++) {
        if (Max < dp[i]) Max = dp[i];
    }
    
    printf("%d", Max);
 
    return 0;
 
}