Solving Dynamic Programming Coding Problems

Solving Dynamic Programming coding problems with explanation

Photo on Wikipedia

1. Problem list

1. Kadane’s Algorithm (Maximum Subarray) G4G, Leetcode Easy
2. Longest continuous increasing subsequence G4G Leetcode Easy
3. Stock buy and sell G4G Leetcode Easy
4. Longest common subsequence G4G Medium

2. C++ Implementation

Kadane’s Algorithm

int maxSubArraySum(int a[], int n){
    int result = INT_MIN, currentSum = 0;
    for(int i = 0; i < n; i++){
        currentSum += a[i];
        if (result < currentSum)
            result = currentSum;
//if < 0, it's meaningless to add it, so set to 0
        if (currentSum < 0)
            currentSum = 0;
    }
    return result;
}

Explanation

1. This is an optimization problem, which can be usually solved by DP.
2. Init result with INT_MIN as the final result can be a negative number (Need to ask what to return if the size is 0 though)
3. Init currentNum with 0 as adding a negative number to another number only makes it smaller.
4. Time Complexity: O(n)

Longest continuous increasing subsequence

Given an unsorted array of integers, find the length of the longest continuousincreasing subsequence (subarray).

//My first attmpt
int findLengthOfLCIS(vector<int>& nums) {
    if (nums.size() < 1) return 0;
    
    int result = 1, start = 0, end = 0;
    int last = nums[0];
    for(int i = 1; i < nums.size(); i++){
        if(nums[i] > last){
            end = i;
            result = result > end - start + 1? result: end - start + 1;
        }else{
            start = end = i;
        }
        last = nums[i];
    }
    return result;
}
// Optimized (run time doesn't change though:( )
int findLengthOfLCIS(vector<int>& nums) { 
    if (nums.size() < 1) return 0;
    int result = 1, start = 0;
    for(int i = 1; i < nums.size(); i++){
        if(nums[i] <= nums[i-1]){
            start = i;
        }
        result = result > i - start + 1? result: i - start + 1;
    }
    return result;
}

Explanation

1. This is another DP problem similar to the first 1 above.
2. Reset the start position when the current value is no longer larger than the previous value.

Stock buy and sell

Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. Can’t sell before you buy.

int maxProfit(vector<int>& prices) {
    if (prices.size() < 1) return 0;
    int maxProfit = 0; //buying and selling on same day is allowed
    int min = prices[0];
    for(int i = 1; i < prices.size(); i++){
        if(maxProfit < prices[i] - min){
            maxProfit = prices[i] - min;
        }
        if(min > prices[i])
            min = prices[i];
    }
    return maxProfit;
}

Explanation

1. This is to find the maximum difference between two elements such that the larger element appears after the smaller number.
2. Instead of taking the difference of the picked element with every other element (Brute force), we take the difference with the minimum element found so far. So we need to keep track of 2 things:
   1) Maximum difference found so far (maxProfit).
   2) Minimum number visited so far (min).
3. Need to check if buying and selling on the same day is allowed or not. if is allowed, the minimum profit is 0, otherwise, it can be a negative number.
4. Time Complexity: O(n), Auxiliary Space: O(1)

The moments where I got stuck

1. The brute force method is easy to come up with, but I forced too much on figuring out how to get the max diff of the crest and trough as there may be multiple crests and troughs.
2. The most important thing here is to figure out how to track maxProfit, specifically, I had no idea of what to compare with for each element (keep track of min).
3. If we take a close look at the implementation, it is very similar to Kadane’s Algorithm.

For more DP coding questions, please check Leetcode, G4G, and Techie Delight.