剑指Offer第三十题：连续子数组的最大和

使用动态规划来求解使用一个临时变量tempsum,返回值是sum遍历整个数组，当tempsum>0时，tempsum加上下一个数组元素，当tempsum小于等于0时，tempsum = 下一个数组元素的值。每遍历一个结点更新sum的值，取tempsum和sum 的较大值 最大值有两种来源，当前值或者前边的字段和加当前值 public class Solution { public int FindGreatestSumOfSubArray(int[] array) { int sum = Integer.MIN_VALUE; int tempsum = 0; for(int i = 0; i<array.length; i++){ if(tempsum < 0){ tempsum = array[i]; }else{ tempsum += array[i]; } sum = Math.max(sum,tempsum); } return sum; } }

延伸问题： 最大子段乘： 方案与这个题一样，只是需要记录max和min，因为最小值如果是负的话，下一次乘一个负数可能变成最大值 最大值有三种来源：前边的乘积乘以当前值，前边的最小值乘以当前值，当前值

public static void getSubArrMul(int [] array) { int res = 0,tempMax = 0; int max = array[0]; int min = array[0]; for(int i = 1; i<array.length; i++) { tempMax = getMax(max*array[i],min*array[i],array[i] ); min = getMin(max*array[i],min*array[i],array[i] ); max = tempMax; res = Math.max(res, max); } System.out.println(res); } public static int getMax(int a,int b, int c) { return Math.max(Math.max(a, b),c); } public static int getMin(int a,int b, int c) { return Math.min(Math.min(a, b),c); }