

Interview preparation kit, Dynamic Programming

Max Array Sum

• Thought: Each of the dp[i] represent the maximum array sum in arr[0:1] (start side and end side are both included), consider each of the element in array, there will be 2 possibilities, hence the subproblem for DP
  • (1) If we include this element, then the maximum subset [0:i] sum will be arr[i - 2] + arr[i] due to denial of adjacent numbers in subset.
  • (2) If we do not want such element, then the maximum subset [0:i] sum will be arr[i - 1], i.e. querying the closest answer.
• Note: It is usually hard to directly come up with a DP transformation function, rather it will be easier to come up with a recursive / search solution first. Sometimes, padding is needed, do not forget!
• Analysis:
  • Time complexity:O(N)
  • Space complexity: O(N) for the DP array

    int maxSubsetSum(vector<int> arr) 
    {
        int res, n = arr.size();
        vector<int>dp(n + 2, 0); // for padding
    
        // starting from 0
        for(int i = 2; i < n + 2; i++)
        {
            dp[i] = max(dp[i - 2] + arr[i - 2 /*shift padding*/], dp[i - 1]);
        }
    
        return dp.back();
    }
    

Candies

• Thought: through the following steps
  • (1) We can simply see that, the amount of candies each student receives depends on the amount of neighbor's candies, hence the subproblem for DP
    • Collecting the statistical data of "how many CONTINUOUS LOWER ELEMENT" on either the left or right side?
  • (2) Iterate the whole array, the minimum candies that this student requires is max(left_continuous_lower[i], right_continuous_lower[i]) + 1(at least one candy for each student)
    • Think the mountain as an example:

          Score               1 2 3 4 3 2 1
          Left cnt lower      0 1 2 3 0 0 0
          Right cnt lower     0 0 0 3 2 1 0
      

    • Explanation: for student 3(0 base), he should get 3 (+ 1) cadies as minimum since there is 3 continuous less element on the left side and so is right, assigning 1 to the leftmost and rightmost element, we will get the optimum solution being: 1 2 3 4 3 2 1
• Analysis:
  • Time complexity: O(N)
  • Space complexity: O(N) for the DP array

    long candies(int n, vector<int> arr) 
    {
        int m = arr.size();
        vector<ull> left_cont_less_cnt(m, 0);
        vector<ull> right_cont_less_cnt(m, 0);
    
        // init, step (1)
        for(int i = 0; i < m - 1; i++)
        {
            if(arr[i] < arr[i + 1])
            {
                left_cont_less_cnt[i + 1] = left_cont_less_cnt[i] + 1;
            }
        }
    
        for(int i = m - 1; i >= 1; i--)
        {
            if(arr[i - 1] > arr[i])
            {
                right_cont_less_cnt[i - 1] = right_cont_less_cnt[i] + 1;
            }
        }
    
        // dp process, step (2)
        ull res = 0;
    
        for(int i = 0; i < m; i++)
        {
            res += max(left_cont_less_cnt[i], right_cont_less_cnt[i]) + 1;
        }
        return res;
    
    }