微软2013年11月19日面试题目一道
去微软也是有机会的,基础扎实,问的题目都是很基础的,都是平时遇见的题目稍加修改
1.计算数组跳跃的连续的最大和
比如:-1,2,3,5,6,-7,-8,9,2
最大是9
3+6,
9
2.写尽可能多的case
分析:和普通的求连续的和的最大值一样,这里的连续变成了跳跃,道理一样
当连续时:
f(i)=max{a[i],s+a[i],f(i-1)}
f(i):第i个包括i之前的连续的和的最大值;
s:与i连着的前面的连续的和
f(i-1):i前面不包括的i的连续的和的最大值
相当于动态规划,写的不清楚或者有问题请留言,转载指明出处
http://blog.csdn.net/yangjunjiezai/article/details/8220038
public static void main(String[] args) { // TODO Auto-generated method stub int[] d = { 1, 2, 3, -6, 5, 9, -7, 7, -22, 99, 88 }; System.out.println(getMaxSum(d)); } public static int getMaxSum(int[] d) { int max = Math.max(d[0], d[1]); int conOne = d[0]; int conTwo = d[1]; for (int i = 2; i < d.length; i++) { conOne = conOne + d[i++]; if (conOne < 0) { conOne = 0; } if (i < d.length) { conTwo = conTwo + d[i]; if (conTwo < 0) { conTwo = 0; } if (max < Math.max(conTwo, conOne)) { max = Math.max(conTwo, conOne); } } System.out.println(max); } return max; }