# Daily Archives: October 20, 2015

## super set by bit array

This is my try for super set problem given by junmin link.
Given a set of unique characters, generate its superset. example: a, b, c, its superset are:
[[], [c], [b], [c, b], [a], [c, a], [b, a], [c, b, a]]

Normal way is to use recursion. But another way is to use bit array. For {a, b, c}, 001 represents {c}, 110 represents {a, b}. In this way, all we need is to iterate a number from 000 to 111 to get all sets.

```/**
* Created by lipeng on 2015/5/15.
*/
public class SuperSet {
public static void main(String[] args) {
char[] chs = {'a', 'b', 'c', 'd'};
printSuperSet(chs);
}

public static void printSuperSet(char[] chs) {
List<List<Character>> sets = new ArrayList<List<Character>>();
int size = (int)Math.pow(2, chs.length);
for(int i=0; i<size; i++) {
List<Character> list = new ArrayList<Character>();
for(int j=0; j<chs.length; j++) {
if(((1<<j)&i)>0) {
}
}
}
System.out.println(sets);
}

}```

## Best Time to Buy and Sell Stock III

This is from leetcode: link. 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 two transactions.

The solution is to maintain 2 array, maxLeft[], maxRight[]. maxLeft[i] maintains the max profit from price[0],…,price[i] by one transaction. maxRight[i] maintains from price[i],…,price[length-1] by one transaction. Then we find i where we can get max{maxLeft[i]+maxRight[i]}.

Check my code on github: link

## Buy stock to get max profit with at most K times

This is from leetcode, 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 k transactions.

The answer is to use dynamic programming by local and global 2-dimension array to implement dynamic programming:
local[i][j] = max{local[i-1][j]+diff, global[i-1][j-1]+max(diff,0)}
global[i][j] = max{local[i][j], global[i-1][j]}

local[i][j] means we do at most jth transaction at i price. If we already got the max profit at most jth transaction at i-1 price, for local[i][j], we just add price[i]-price[i-1], no matter if it is negative or positive. Another option for local[i][j] is that we get it from global[i-1][j-1]+max(diff,0). If diff is less than 0, we then ignore the transaction price[i]-price[i-1]

global[i][j] could be got from local[i][j] or global[i-1][j], which is easy to understand.

Check my code on github: link