문제 링크

🧐 접근 과정

누적 합 개념을 접한 후 6번째 푸는 문제이다.
이전에 풀었던 문제들은 단순히 수열의 i번째부터 j번째까지의 합을 구하는 것이었다면, 이 문제는 부분 배열 중 각 원소의 합이 가장 큰 부분 배열을 찾는 문제이다. (이를 Maximum Subarray라고 부른다.)

• 다이나믹 프로그래밍을 사용한다.
• dp[i] 는 i 번째 수를 포함하는 부분 수열의 최대 합을 의미한다.

처음에는 dp[i - 1]이 0보다 클 때와 작을 때를 나눠 계산을 했다.

• dp[i - 1] >= 0 이라면, dp[i]는 반드시 dp[i - 1] + arr[i] 이다.
• dp[i - 1] < 0 이라면, dp[i]는 arr[i]가 음수일 때를 고려해 dp[i - 1] + arr[i] 와 arr[i] 중 최댓값이다.

이를 구현하면 아래와 같다.

if (dp[i - 1] >= 0) {
    dp[i] = dp[i - 1] + arr[i];
}
else {  // dp[i - 1] < 0
    dp[i] = getMax(dp[i - 1] + arr[i], arr[i]);  // arr[i]도 음수일 때 고려 
}

그런데, 잘 살펴보면 dp[i - 1]이 0보다 큰지의 여부와 관계없이 코드를 일반화 할 수 있다.

dp[i] = getMax(dp[i - 1] + arr[i], arr[i]);

• 즉, dp[i] = getMax(dp[i - 1] + arr[i], arr[i]);

매 과정마다 max값을 갱신해주면 된다.

📍 주의하기

• 수열은 음수를 포함하므로, max를 선언할 때 0으로 하면 틀린다.

#include <climits>
int max = INT_MIN; 

혹은

int max = -987654321; 

를 사용하자.

😋 후기

이전에 ps 연습을 하다가 부분합을 구하는 과정에서 애를 먹은 적 있다.
이해가 정말 안 돼서 정답만 보고 이해를 포기했었는데, 오랜만에 만난 문제에서 스스로의 힘으로 문제를 해결해 너무 뿌듯하다.
그동안 헛된 시간만 보낸 건 아닌가 보다.
더 열심히 해야지.

💻 코드

// bj10211 - Maximum Subarray
#include <iostream>   
using namespace std;
 
int arr[1001];   
int dp[1001];   // dp[i]는 i를 포함하는 부분 수열의 최대 합

int getMax(int a, int b) {
    if (a >= b) return a;
    else return b;
}

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

    int t, n;
    cin >> t;

    while (t--) { 
        cin >> n;

        int max = -987654321;   

        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
            
            dp[i] = getMax(dp[i - 1] + arr[i], arr[i]); 
            max = getMax(max, dp[i]);
             
        }
        cout << max << "\n";
    }
}