[algorithm] Max Array Sum - 답있음 주의

https://www.hackerrank.com/challenges/max-array-sum/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dynamic-programming

Max Array Sum | HackerRank

안녕하세요 대우니입니다 :)

오랜만에 dp 문제를 풀려고 하니 생각이 안나서 오래걸렸던 문제였습니다.

dp문제 중에서는 쉬운 편(?) 이었던 거 같은데 말이죠.

 

arr = [3, 7, 4, 6, 5] 라 가정합니다.

maxNum 은  i - 2 까지 더해졌던 값 중 가장 큰 값을 의미합니다.

 변하는 값이 아니라 계속 쓰이는 값이기 때문에 저장해둡니다. 

arr	maxNum	sum
3	3	3
7	3	7
4	3	3 + 4 = 7
6	7	7 + 6 = 13
5	7	7 + 5 = 12

따라서 답은 13이 됩니다.

코드는 이렇습니다.

#include <bits/stdc++.h>

using namespace std;

// Complete the maxSubsetSum function below.
int maxSubsetSum(vector<int> arr) {
    vector<int> sum;
    int maxNum = arr[0], answer = arr[0];
    // arr 사이즈가 2보다 작을 경우 부분 집합의 합을 구하는 것이므로 답은 0이 됩니다.
    if(arr.size() <= 2) return 0;
    for(int i = 0; i < arr.size(); i++){
        if(i - 2 < 0)
            sum.push_back(arr[i]);
        else{
            maxNum = max(maxNum, sum[i - 2]);
            // 0보다 작은 수일 경우를 대비했습니다. 
            int num = max(max(maxNum + arr[i], maxNum), arr[i]);
            if(answer < num) answer = num;
            sum.push_back(num);
        }
    }
    return answer;
}