一个整数数组，其中所有数字都大于等于1。这些数字可以用加号，乘号和括号连接成一个表达式，求表达式的最大值。二维DP搞定。
Follow up是考虑0和负数。这时需要维护两个DP表，同时跟踪表达式的最大值和最小值。在当今这个DP已经不流行的年代，这个题目算是我所有面试见到的最难DP题目了。
Onsite一共4轮，里面有一个中国人，一个ABC，两个白人。中午一个senior level的国女陪着吃饭，感觉面试阵容实在太好了。
第一面是LC原题，根据前序遍历和中序遍历构造二叉树，follow up是检测非法输出。以前没想过follow up，原来还挺有意思的。
第二面有两题。第一题是Amicable pair，我只给出了O(N*sqrt(N))的暴力解法，不过小白还是很满意的，他说这已经是他所知的最好解法了。第二题是实现字典树，也不难。
第三面是实现Bipartite。虽然图论方面的知识已经基本都忘了，白人经理很耐心的引导我，排除了我一些错误的想法（例如想边BFS边回溯），然后自己debug了一下，主要的test case都过了。不过由于debug花了些时间，没有follow up。估计要挂就挂在这一轮了。
第四面是实现BigInteger类，主要实现BigInteger之间的加法。由于正负数都要考虑，其实这里也要实现求相反数和减法。思路不难，但是代码还挺多的，test case也挺多的，不过都测对了。
