学步园

微软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;

	}