백준 알고리즘, 1912 문제

---

풀이

연속합 문제는 3중 for 문을 구성해야 풀 수 있다.

기억할 연산값을 저장하는 DP 배열에

10

10 + -4

10 + -4 + 3 

...

-4

-4 + 3

-4 + 3 + 1

...

12

12 + 21

12 + 21 + -1 

이렇게 모든 값을 비교해보려면

3중 for 문이 필요했다..

그러나 1 개의 생각만 하면 하나의 for 문으로 문제를 해결할 수 있다.

값을 더해나가는 sum 값이 음수이면 초기화 시킨다.

이전 까지 아무리 큰 값이 나왔더라도 다음에 나올 값이 음수라면

지금까지 더한 값은 최대값이 될 수 없기 때문이다.

해답을 보고나니 너무나 당연한 이론인데

왜 생각해내지 못했을까 싶었다.

---

코드

@github 에서 보기

/**
 * @site: https://www.acmicpc.net/problem/1912
 * @github: https://github.com/7772
 * @auth: Landon Park
 * @date: 2018. 08. 03
 */
#include <iostream>
using namespace std;
int main() {
    int arr[100001];
    int sum = 0, result = -2100000000;
    int i, T;
    cin >> T;
    for (i = 1; i <= T; i++) cin >> arr[i];
    for (i = 1; i <= T; i++) {
        if (sum + arr[i] > 0) {
            sum += arr[i];
            result = max(result, sum);
        }
        else {
            result = max(result, sum + arr[i]);
            sum = 0;
        }
    }
    cout << result << endl;
}

# 처음 작성한 민망한 3중 for 문

/**
 * @site: https://www.acmicpc.net/problem/1912
 * @github: https://github.com/7772
 * @auth: Landon Park
 * @date: 2018. 08. 03
 */
#include <iostream>
using namespace std;

int max(int a, int b) {
    return (a > b) ? (a) : (b);
}
int main() {
    int n;
    int arr[100001];
    int DP[100001];
    int i, j, k;
    int max = -2147483648, sum = 0;
    cin >> n;
    for (i = 1; i <= n; i++) cin >> arr[i];
    for (i = 1; i <= n; i++) {
        DP[i] = -2147483648;
        for (j = i; j <= n; j++) {
            sum = 0;
            for (k = i; k <= j; k++) {
                sum += arr[k];
            }
            if (DP[i] < sum) DP[i] = sum;
        }
        if (max < DP[i]) max = DP[i];
    }

    cout << max << endl;
    return 0;
}