[해커랭크] Max Array Sum (C++)

문제 링크: 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

1. 주의할 점

- DP로 풀지 않고 일반 DFS로 풀 경우, TLE발생

- DFS + DP 즉, 메모이제이션으로 풀 수 있다

 

2. 구현

- DP[][]배열을 통해 [현재 Index][현재 Arr[]값 사용 여부] 형태로 최대값을 저장한다. 단, Arr[] 벡터의 최대 길이가 10000이며 DP점화식에서 앞의 2개의 DP 배열을 이용해서 식을 구한다는 가정하에 10000+2로 배열의 크기를 설정했다.

- DP[][] 배열의 두 번째 인자로 0이면 현재 값을 사용하지 않으며, 1이면 현재 값을 사용한다는 의미다

- Val을 통해 Arr[i]와 0을 비교하여 음수가 아닌 값을 가지도록 한다

- DP[i][0]은 현재 값을 사용하지 않으므로, 이전 DP의 [][0], [][1]을 비교하여 큰 값을 할당한다

- 만약 i가 0이라면, 가장 초기이므로 DP[2][1]에는 Val을 할당한다

- i가 양의 정수라면, 현재 값을 사용할 때 Arr[i-1]이 음수 or 양수일때를 구분한다

- 음수라면, 0을 더했기 때문에 DP[i][0]을 구할때와 똑같이 한다

- 양수라면, Arr[i-1]을 더했기 때문에, 이전 DP에서 [][0]과 2개전 DP[][1]을 비교하여 큰 값을 할당한다

- 추가로, 현재 값을 더하기 때문에 Val을 더해준다

- 마지막으로, For문이 끝난 이후 DP[len+1][0], DP[len+1][1]을 비교하여 큰 값을 Return한다

int dp[100002][2];      //[][0]: X, [][1]: O
// Complete the maxSubsetSum function below.
int maxSubsetSum(vector<int> arr) {
    int result=0;
    int len = arr.size();
    for(int i=0;i<len;i++){
        int val = max(0,arr[i]);
        dp[i+2][0] = max(dp[i+1][1], dp[i+1][0]);
        if(i==0)
            dp[i+2][1] = val;
        else{
            if(arr[i-1]<0)     //이전 값이 음수여서 안 더한 경우
                dp[i+2][1] = val + max(dp[i+1][1],dp[i+1][0]);           
            else
                dp[i+2][1] = val + max(dp[i+1][0], dp[i][1]);            
        }
    }
    return max(dp[len+1][0],dp[len+1][1]);
}