[알고리즘] 리트코드 최대하위배열 c++ // dp

* 의사코드

- dp[i] : i번째까지 부분수열중 최대합

2가지 경우의수가 있다.

i) 이전값을 버리고, 새로시작하는경우

ii) 이전값에서 나를 더하는경우

둘중에서 큰값을 택하면된다.

* 전체코드

int dp[100000+4];
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        dp[0]=nums[0];
        for(int i=1;i<nums.size();++i){
            dp[i]=max(dp[i-1]+nums[i],nums[i]);
        }
        return *max_element(dp,dp+nums.size());
    }
};

 

* 번외 : 탑다운 dp

- 완탐재귀

class Solution {
public:
    int maxSubArray(vector<int>& nums) {    
        return solve(nums, 0, false);
    }
    int solve(vector<int>& A, int i, bool mustPick) {
		// our subarray must contain atleast 1 element. If mustPick is false at end means no element is picked and this is not valid case
        if(i >= size(A)) return mustPick ? 0 : -1e5;       
        if(mustPick)
            return max(0, A[i] + solve(A, i+1, true));                  // either stop here or choose current element and recurse
        return max(solve(A, i+1, false), A[i] + solve(A, i+1, true));   // try both choosing current element or not choosing
    }
};

중복계산이 많음

                                                f(0, False)                       🔽 => repeated calculations
					                          /             \ 
                       		       f(1, False)              f(1, True)
			                      /          \       🔽          \      🔽
			                 f(2, False)      f(2, True)           f(2, True)
							/            \  🔽       \   🔽           \  🔽
						f(3, False)   f(3,True)     f(3, True)           f(3, True)
						/        \            \           \                  \
				      ...        ...          ...         ...                ...

따라서 우리는 여기서 메모이제이션 기법을 사용하여 솔루션을 더 효율적으로 만들 수 있습니다. 여기서 우리는 dp배열을 사용하는데, 여기서 dp[mustPick][i]는 에서 시작하는 최대 합 부분 배열을 나타내고 i는 mustPick현재 요소를 강제로 선택해야 하는지 여부를 나타냅니다.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {    
        vector<vector<int>> dp(2, vector<int>(size(nums), -1));
        return solve(nums, 0, false, dp);
    }
    int solve(vector<int>& A, int i, bool mustPick, vector<vector<int>>& dp) {
        if(i >= size(A)) return mustPick ? 0 : -1e5;
        if(dp[mustPick][i] != -1) return dp[mustPick][i];
        if(mustPick)
            return dp[mustPick][i] = max(0, A[i] + solve(A, i+1, true, dp));
        return dp[mustPick][i] = max(solve(A, i+1, false, dp), A[i] + solve(A, i+1, true, dp));
    }
};