SnapChat 电面挂经

recursion 代码
public static int maxSumOfA(int[] nums, int i, int j){
                if(i == j){ return nums[i];}
                if(j - i == 1){ return Math.max(nums[i], nums[j]);}
               
                int candidate1 = nums[i] +
                                (nums[i+1] > nums[j] ? maxSumOfA(nums, i+2, j) : maxSumOfA(nums, i+1, j-1));
                int candidate2 = nums[j] +
                                (nums[i] > nums[j-1] ? maxSumOfA(nums, i+1, j-1) : maxSumOfA(nums, i, j-2));
                return Math.max(candidate1, candidate2);
        }

Mark6 发表于 2016-4-21 10:21
recursion 代码
public static int maxSumOfA(int[] nums, int i, int j){
                if(i == j){ return nums;}
...

感谢分享。我想再问下递归的话时间复杂度大概是多少呢，我不太确定。谢谢

jy_121 发表于 2016-4-21 11:19
感谢分享。我想再问下递归的话时间复杂度大概是多少呢，我不太确定。谢谢

exponential, 2^n, 因为长度为n的问题，需要两个长度为n-1的子问题的结果。所以 T（n） = 2 T(n-1) + c

补充内容 (2016-4-21 11:45):
T（n） = 2 T(n-2) + c

Mark6 发表于 2016-4-21 11:44
exponential, 2^n, 因为长度为n的问题，需要两个长度为n-1的子问题的结果。所以 T（n） = 2 T(n-1) + c

...

好的，谢谢。

我面优步就类似这个题，但是不同的是B也是用A的方法来取数字，套路好深-。-

1. public class CoinsInLine {
   
2.        
   
3.         public int maxCoins(int[] coins) {
   
4.                 int first = coins[0] + max(coins, 1, coins.length - 1);
   
5.                 int last = coins[coins.length - 1] + max(coins, 0, coins.length - 2);
   
6.                 return Math.max(first, last);
   
7.         }
   
8.        
   
9.         private int max(int[] coins, int left, int right) {
   
10.                 if (left == right) {
    
11.                         return 0;
    
12.                 }
    
13.                 if (coins[left] > coins[right]) {
    
14.                         left++;
    
15.                 } else {
    
16.                         right--;
    
17.                 }
    
18.                 int first = coins[left] + max(coins, left + 1, right);
    
19.                 int last = coins[right] + max(coins, left, right - 1);
    
20.                 return Math.max(first, last);
    
21.         }
    
22.        
    
23.         public static void main(String[] args) {
    
24.                 CoinsInLine solution = new CoinsInLine();
    
25.                 int[] coins = {3, 7, 2, 1};
    
26.                 System.out.println(solution.maxCoins(coins));
    
27.         }
    
28. }

复制代码

大半夜的，只能想出来recursive的解法，第一反应是dp，但是死活想不出来

第一反应递归，关键确定下一层递归的子串。

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int maxSumA(int nums[], int b, int n){//b is beginning
   
5.         //edge case
   
6.         if(n <= b) return 0;
   
7.         if(n - b == 1) return nums[b];
   
8.        
   
9.         int sumA = 0;
   
10.         //One is that A select the first number
    
11.         sumA += nums[b];
    
12. 
    
13.         if(nums[b+1] < nums[n-1])//Determine B's choice
    
14.                 sumA += maxSumA(nums, b+1, n-1);
    
15.         else
    
16.                 sumA += maxSumA(nums, b+2, n);
    
17.                
    
18.         int sum = sumA;
    
19.        
    
20.         //The other is that A select the last number
    
21.         sumA = nums[n-1];
    
22.         if(nums[b] < nums[n-2])//Determine B's choice
    
23.                 sumA += maxSumA(nums, b, n-2);
    
24.         else
    
25.                 sumA += maxSumA(nums, b+1, n-1);
    
26.        
    
27.         return sum > sumA? sum: sumA;
    
28. }
    
29. int main(){
    
30.         int nums[] = {3, 7, 2, 1};
    
31.         cout << maxSumA(nums, 0, 4) << endl;
    
32.         return 0;
    
33. }
    

复制代码

有个问题，如果是[5, 7, 8, 5]这个subarray， B先拿，那么它会拿哪个？如果B拿第一个5，那么A可以在剩下的拿到12，如果B拿最后一个5，那么A可以拿到13。怎么处理这种情况？

就一道题？

思路大概是这个样，当有一个一个元素时，trivial，有两个元素时，取大的那个。有n(n > 2)个元素时，模拟一轮A， Bpick的过程，然后取剩下的最大的那个。