Subset Sum

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

Examples: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output:  True  //There is a subset (4, 5) with sum 9.

Java (bottom-up)
Time complexity: O(N*M), N – size of array, M – target sum
Space complexity: O(N*M), N – size of array, M – target sum

public class SubSetSum {

    public boolean sumsTo(int[] nums, int sum){
        if (nums == null || nums.length == 0 || sum < 0){
            return false;
        }

        boolean[][] dp = new boolean[nums.length][sum+1];

        for (int i = 0; i < nums.length; ++i){
            dp[i][0] = true;
        }

        for (int i = 0; i < dp.length; ++i){
            for (int j = 1; j < dp[0].length; ++j){
                if (i == 0 && nums[i] == j){
                    dp[i][j] = true;
                } else if (i == 0){
                    continue;
                }else {
                    dp[i][j] = dp[i-1][j] || (nums[i] <= j ? dp[i-1][j - nums[i]] : false);
                }

            }
        }

        return dp[nums.length - 1][sum];
    }

}

Python (top-down)
Time complexity: O(2^N), N – size of array
Space complexity: O(N), N – size of array

def sumsTo(nums, sum):
    if not len(nums) or sum < 0:
        return False

    dp = [None] * len(nums)
    return checkSumsTo(nums, 0, sum, dp)

def checkSumsTo(nums, idx, sum, dp):
    if sum == 0:
        return True
    elif sum < 0 or idx >= len(nums):
        return False
    elif idx < len(nums) and dp[idx]:
        return dp[idx]

    notInclude = checkSumsTo(nums, idx+1, sum, dp)
    include = checkSumsTo(nums, idx+1, sum - nums[idx], dp)
    dp[idx] = notInclude or include

    return dp[idx]

Lintcode. Best Time to Buy and Sell Stock IV

 
Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most transactions.

You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example

Given prices = [4,4,6,1,1,4,2,5], and k = 2, return 6.

Java
Time complexity: O(K*N^2), N – number of days, k – number of transactions
Space complexity: O(N*K), N – number of days, k – number of transactions

class Solution {
    /**
     * @param k: An integer
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int k, int[] prices) {
        // write your code here
        if (prices == null || prices.length == 0){
            return 0;
        }
        
        if (k >= prices.length) {
    		int profit = 0;
    		for (int i = 1; i < prices.length; i++) { if (prices[i] > prices[i - 1]) {
    				profit += prices[i] - prices[i - 1];
    			}
    		}
    		return profit;
    	}
        
        int[][] dp = new int[k+1][prices.length];
        
        for (int i = 1; i < dp.length; ++i){
            int profit = 0;
            for (int j = 1; j < dp[0].length; ++j){
                for (int m = 0; m < j; ++m){
                    profit = Math.max(profit, prices[j] - prices[m] + dp[i-1][m]);
                }
                dp[i][j] = Math.max(dp[i][j-1], profit);       
            } 
            
        }
        
        return dp[k][prices.length - 1];
    }
}

Java (optimized)
Time complexity: O(K*N), N – number of days, k – number of transactions
Space complexity: O(N*K), N – number of days, k – number of transactions

class Solution {
    /**
     * @param k: An integer
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int k, int[] prices) {
        // write your code here
        if (prices == null || prices.length == 0){
            return 0;
        }
        
        if (k >= prices.length) {
    		int profit = 0;
    		for (int i = 1; i < prices.length; i++) {
    			if (prices[i] > prices[i - 1]) {
    				profit += prices[i] - prices[i - 1];
    			}
    		}
    		return profit;
    	}
        
        int[][] dp = new int[k+1][prices.length];
        
        for (int i = 1; i < dp.length; ++i){
            int profit = 0;
            int maxDiff = -prices[0];
            for (int j = 1; j < dp[0].length; ++j){
                dp[i][j] = Math.max(dp[i][j-1], prices[j] + maxDiff); 
                maxDiff = Math.max(maxDiff, dp[i-1][j] - prices[j]);
            } 
            
        }
        
        return dp[k][prices.length - 1];
    }
}

Lintcode. Longest Common Subsequence

Given two strings, find the longest common subsequence (LCS).
Your code should return the length of LCS.

Clarification
What’s the definition of Longest Common Subsequence?

https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Example
For “ABCD” and “EDCA”, the LCS is “A” (or “D”, “C”), return 1.
For “ABCD” and “EACB”, the LCS is “AC”, return 2.

 

Java (bottom-up)
Time complexity: O(N*M), N – len of string1, M – len of string2
Space complexity: O(N*M), N – len of string1, M – len of string2

public class Solution {
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    public int longestCommonSubsequence(String A, String B) {
        // write your code here
        if (A == null || B == null || A.length() == 0 || B.length() == 0){
            return 0;
        }
        
        int[][] dp = new int[A.length()][B.length()];
        
        for (int i = 0; i < A.length(); ++i){
            for (int j = 0; j < B.length(); ++j){
                if (i == 0){
                    dp[i][j] = A.charAt(i) == B.charAt(j) ? 1 : 0;
                } else {
                    int same = A.charAt(i) == B.charAt(j) ? 1 : 0;
                    if (same == 1){
                        dp[i][j] = same + ((i > 0 && j > 0) ? dp[i-1][j-1] : 0);
                    } else{
                        int prevNonSymm1 = j > 0 ? dp[i][j-1] : Integer.MIN_VALUE; 
                        int prevNonSymm2 = i > 0 ? dp[i-1][j] : Integer.MIN_VALUE;
                        dp[i][j] = Math.max(prevNonSymm1, prevNonSymm2);   
                    }
                }
            }    
        }
        return dp[A.length()-1][B.length() - 1];
    }
}

 

Python (bottom-up)

class Solution:
    """
    @param A, B: Two strings.
    @return: The length of longest common subsequence of A and B.
    """
    def longestCommonSubsequence(self, A, B):
        # write your code here
        if (not len(A) or not len(B)):
            return 0
            
        dp = [[0 for x in range(len(A))] for y in range(len(B))] 
        
        for x in range(len(A)):
            for y in range(len(B)):
                if A[x] == B[y]:
                    dp[x][y] = 1 if not x or not y else 1 + dp[x-1][y-1]
                elif (x > 0 and y > 0):
                    dp[x][y] = max(dp[x-1][y], dp[x][y-1])
                else: 
                    dp[x][y] = dp[x-1][y] if x else dp[x][y-1] if y else 0

        return dp[len(A)-1][len(B)-1]

Java (topdown)
Time complexity: O(N*M), N – len of string1, M – len of string2
Space complexity: O(N*M) (dp array) + O(N*M) (recursive stack), N – len of string1, M – len of string2

public class Solution {
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    public int longestCommonSubsequence(String A, String B) {
        // write your code here
        if (A == null || B == null || A.length() == 0 || B.length() == 0){
            return 0;
        }
        
        int[][] dp = new int[A.length()][B.length()];
        
        return lcs(A, B, 0, 0, dp);
    }
    
    private int lcs(String A, String B, int idxa, int idxb, int[][] dp){
        if (idxa == A.length() || idxb == B.length()){
            return 0;
        }
        
        if (dp[idxa][idxb] != 0){
            return dp[idxa][idxb];
        }
        
        int lcsLen = 0;
        
        if (A.charAt(idxa) == B.charAt(idxb)){
            lcsLen = 1 + lcs(A, B, idxa+1, idxb+1, dp);    
        } else {
            lcsLen = Math.max(lcs(A, B, idxa+1, idxb, dp), lcs(A, B, idxa, idxb+1, dp)); 
        }
        
        dp[idxa][idxb] = lcsLen;
        
        return lcsLen;
    }
}