Microsoft | OA - 2020 | Max Even Sum Subsequence Of Length K | DP | Top Down➡️Bottom Up | Clean Code

11/17/2024

Round 1

Questions: Given an array nums[] consisting of N positive integers, and an integer K, the task is to find the maximum possible even sum of any subsequence of size K. If it is not possible to find any even sum subsequence of size K, then print -1.

Input: nums[] = {4, 2, 6, 7, 8}, K = 3
Output: 18
Explanation: Subsequence having maximum even sum of size K = 3 is {4, 6, 8}.
Therefore, the required output is 4 + 6 + 8 = 18.

Input: nums[] = {5, 5, 1, 1, 3}, K = 3
Output: -1

Candidate's Approach

Approach 1 : Using Top Down DP (Recursion To Memoization)

class TopDown {
    int n;

    // O(2^N) & O(N)
    int solveWithoutMemo(vector<int>& nums, int index, int k, int sum) {
        if(k == 0)
            return (sum % 2 == 0) ? sum : 0;
        if(index == n)
            return 0;

        int currSkip = solveWithoutMemo(nums, index + 1, k, sum);
        int currTake = solveWithoutMemo(nums, index + 1, k - 1, sum + nums[index]);
        
        return max(currSkip, currTake);
    }

    // O(2*N*K*TS) & O(N*K*TS + N)
    int solveWithMemo(vector<vector<vector<int>>>& dp, vector<int>& nums, int index, int k, int sum) {
        if(k == 0)
            return (sum % 2 == 0) ? sum : 0;
        if(index == n)
            return 0;

        if(dp[index][k][sum] != -1)
            return dp[index][k][sum];

        int currSkip = solveWithMemo(dp, nums, index + 1, k, sum);
        int currTake = solveWithMemo(dp, nums, index + 1, k - 1, sum + nums[index]);
        
        return dp[index][k][sum] = max(currSkip, currTake);
    }

public: 
    int maxEvenSumSubseqLengthK(vector<int>& nums, int k) {
        n = nums.size();
        int totalSum = accumulate(begin(nums), end(nums), 0);
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(k + 1, vector<int>(totalSum + 1, -1)));
        int maxEvenSum = solveWithMemo(dp, nums, 0, k, 0);
        return (maxEvenSum == 0) ? -1 : maxEvenSum;
    }
};

Approach 2 : Using Bottom Up DP (3D + 2D Tabulation)

class BottomUp {
public:
    int maxEvenSumSubseqLengthK_V1(vector<int>& nums, int k) {
        int n = nums.size();
        int totalSum = accumulate(begin(nums), end(nums), 0);
        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(k + 1, vector<int>(totalSum + 1, 0)));

        for(int index = 0; index <= n; ++index)
            for(int sum = 0; sum <= totalSum; ++sum)
                dp[index][0][sum] = (sum % 2 == 0 ? sum : 0);

        for(int index = n-1; index >= 0; --index) {
            for(int curr_k = 1; curr_k <= k; ++curr_k) {
                for(int sum = totalSum; sum >= 0; --sum) {
                    int currSkip = dp[index + 1][curr_k][sum]; 
                    int currTake = dp[index + 1][curr_k - 1][sum + nums[index]];
                    dp[index][curr_k][sum] = max(currSkip, currTake);
                }
            }
        }

        int maxEvenSum = dp[0][k][0];
        return (maxEvenSum == 0) ? -1 : maxEvenSum;
    }

    int maxEvenSumSubseqLengthK_V2(vector<int>& nums, int k) {
        int n = nums.size();
        int totalSum = accumulate(begin(nums), end(nums), 0);
        vector<vector<int>> nextRow(k + 1, vector<int>(totalSum + 1, 0)), idealRow(k + 1, vector<int>(totalSum + 1, 0));

        for(int sum = 0; sum <= totalSum; ++sum)
            nextRow[0][sum] = (sum % 2 == 0 ? sum : 0);

        for(int index = n-1; index >= 0; --index) {
            for(int curr_k = 1; curr_k <= k; ++curr_k) {
                for(int sum = totalSum; sum >= 0; --sum) {
                    idealRow[0][sum] = (sum % 2 == 0 ? sum : 0);
                    int currSkip = nextRow[curr_k][sum];
                    int currTake = nextRow[curr_k - 1][sum + nums[index]];
                    idealRow[curr_k][sum] = max(currSkip, currTake);
                }
            }
            nextRow = idealRow;
        }

        int maxEvenSum = nextRow[k][0];
        return (maxEvenSum == 0) ? -1 : maxEvenSum; 
    }
};

Interviewer's Feedback

No feedback provided.