google 面试一道 求大神帮忙解解

        public  int findMaxSum(Stack<Integer> stack1,Stack<Integer> stack2,int n){
                if(n == 0 || (stack1.isEmpty() && stack2.isEmpty())){
                        return 0;
                }
                int res = 0;
                if(!stack1.isEmpty()){
                        int temp = stack1.pop();
                        int sum = temp + findMaxSum(stack1,stack2,n-1);
                        if(res < sum){
                                res = sum;
                        }
                        stack1.push(temp);
                }
                if(!stack2.isEmpty()){
                        int temp = stack2.pop();
                        int sum = temp + findMaxSum(stack1,stack2,n-1);
                        if(res < sum){
                                res = sum;
                        }
                        stack2.push(temp);
                }
                return res;
        }
用递归写了一个，不知道有没有DP的解法
看错了，是k个stack，上面的做法是2个的，k个的一样的思路

public static int findMaxSum(List<Stack<Integer>> stacks,int n){

                if(n == 0){

                        return 0;

                }

                int length = stacks.size();

                int res = Integer.MIN_VALUE;

                for(int i=0;i<length;i++){

                        Stack<Integer> cur = stacks.get(i);

                        if(!cur.isEmpty()){

                                int temp = cur.pop();

                                int sum = temp + findMaxSum(stacks,n-1);

                                if(sum > res){

                                        res = sum;

                                }

                                cur.push(temp);

                        }

                }

                return res;

        }

宝贝忆彼岸 发表于 2015-11-10 02:17
public  int findMaxSum(Stack stack1,Stack stack2,int n){
                if(n == 0 || (stac ...

你这是从stack1取一个，然后从stack2取下一个吧？楼主取的N个是不是都必须出自同一个stack？而且是stack顶部？

理解错题了。

感觉像是NP问题，只能用recusrion去try所有取法的combination? 是不是还有别的条件。。。

n等于2的时候不是700+10吗

hu4 发表于 2015-11-10 02:11
n等于2的时候不是700+10吗

stack 是说要先取出上面的coin，之后才能拿下面的。

题意大概就是有k堆coin，拿n个，但是是最上面的n个(可以是不同堆)

宝贝忆彼岸 发表于 2015-11-10 02:17
public  int findMaxSum(Stack stack1,Stack stack2,int n){
                if(n == 0 || (stack1.isEmpty() && stack ...

原题是k stacks吧

一个简单解法是：
假设我从stack1里面取A个数 stack2里取B个数。 A+B=n 求怎么去解这个A和B。
再仔细想，就首先算出如果都从A取的sum数组 比如这个题是[0,1, 5, 705, 708] 然后再算出都从B取i个数的sum的数组。[0,5, 15,21]
然后根据n的值 two pointers。互相移动 然后keep track max就好了。

For k stacks...求楼下支招。

xiaozhuxiaozhu 发表于 2015-11-10 02:23
原题是k stacks吧

哦哦，对，看错了，不过k个也是一样的解法，回复里面改正了

宝贝忆彼岸 发表于 2015-11-10 02:55
哦哦，对，看错了，不过k个也是一样的解法，回复里面改正了

这个方法太好了！想了半天没弄明白时间复杂度该怎么分析呢？