爱奇艺-推荐算法面试

算法题： 1.给定两个字符串A，B 写一个方法将A中含有B子串剔除（现在没查找求解方法）2.给定一个无序的整数数组，第i个元素只能和其右边的元素进行比较，按照这种方式数组中两个元素之间的最大差（好像是编程之美里的题）

---

对于第二道算法题的解题思路：

定义两个变量currMax、max，currMax记录的是当前位置之前的数组中的最大值，max记录当前的最大差 public int getMax(int[] arr){ if(arr.length < 2){ return -1; } int max = 0; int currMax = arr[0]; for(int i = 1; i < arr.length; i++){ if(arr[i] > currMax){ currMax = arr[i]; }else{ max = Math.max(max,currMax-arr[i]); } } return max; }

2.通过动态规划来做 定义s[i]为第i个元素和其右边元素之差的最大值 则转移方程为： （1）s[i+1]<0时，说明第i+1个原始是第i+1到第n个元素间的最小值 s[i] = arr[i]-arr[i+1] (2) s[i+1] >= 0时，s[i] = s[i+1] + arr[i] - arr[i+1]

public int getMax(int[] arr){ if(arr.length < 2){ return -1; } int[] result = new int[arr.length]; result[arr.length-1] = 0; for(int i = arr.length-2; i >= 0; i--){ if(result[i+1] <= 0){ result[i] = arr[i] - arr[i+1]; }else{ result[i] = result[i+1] + arr[i] - arr[i+1]; } } }