Dynamic Programming based on L.I.S / Stocks

DP Problems based on L.I.S

Longest Increasing Subsequence (L.I.S)

In above solution we notice that if we are concerned about only the `length` of LIS and not the actual LIS , we can use a different approach, which which further reduce our time complexity

Largest Divisible Subset

This problem can be formulated as a varitation of print LIS problem

Longest String Chain

Longest Bitonic Subsequence

Number of Longest Increasing Subsequence

The problem is exactly same as LIS with an additional corner case of handling EQUAL length subsequences

DP Problems based on Stocks

Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock II (Infinite transactions allowed)

in this problem even a greedy solution will work , the ideal is to accumulate each and every viable profit -just because we can

we collect every single upstroke, we notice that BUY is always after a dip , and SELL is before the dip

Best Time to Buy and Sell Stock IV

To formulate the bottom up solution, consider a matrix of (days elapsed) x (number of transaction allowed)

• we know no matter how many transactions are allowed , withing a single day we can make ZERO profit , as every transaction buys and sells at the same day - so 0th column is zero

• we know if NO transactions are allowed , we cannot make any profit - so 0th row is zero

  

• Let dp[i][j] represent maximum profit that can be obtained by jth day , assuming a maximum of i transactions allowed

• dp[i][j] can be obtained by doing no transactions on day j and simply taking into account dp[i][j-1] ie i transactions were done by previous day itself

• dp[i][j] can be obtained by doing ONE transactions on day j and simply taking into account dp[i-1][j-1] ie the ith transaction is between j-1 the and jth day

• dp[i][j] can be obtained by doing ONE transactions on day j and simply taking into account dp[i-1][j-2] ie the ith transaction is between j-2 the and jth day

• dp[i][j] can be obtained by doing ONE transactions on day j and simply taking into account dp[i-1][j-3] ie the ith transaction is between j-3 the and jth day

• and so on .... we need to take MAXIMUM of all these profit options

  

  

• 

we can optimise it even further actually , looking at the calculations closely we only need maximum among dp[i-1][k]- prices[k] which we can actually maintain

Best Time to Buy and Sell Stock III

This solution can also be formulated through divide and conquer, we can divide the problem of these two optimal transactions, as most optimal on the left and most optimal on the right and then combine the two

Best Time to Buy and Sell Stock with Transaction Fee(Infinite transactions)

Best Time to Buy and Sell Stock with Cooldown