剑指offer——连续子数组的最大和

题目描述

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？(子向量的长度至少是1)

思路：用dp。 每次num往后面加，如果小于0.则置为0，后面的重新从那个数开始。如果加的大于max就更新max。

注意需要判定是不是全部为负数。为负数 需要把最小的负数给它返回

import java.util.Arrays; public class Solution { public int FindGreatestSumOfSubArray(int[] array) { if(array.length==0)return 0; int len = array.length; int num[] = new int [len]; int max = array[0]; num[0] = max; for(int i =1;i<len;i++){ int temp = array[i]; num[i] =num[i-1]+temp; if(num[i]>=0){ }else { num[i]=0; } max = max>num[i]?max:num[i]; }//for if(max==0){//全部为负数的情况 Arrays.sort(array); return array[len-1]; } return max; } }

不能用Arrays.sort 时间复杂度至少为nlogn了：

只需要稍微改一改  就可以了，本想把max初始赋值为Integer.MINVALUE或是0x80000000具体指最小的负数(-0)，它们指的是同一个数但是结果有误，暂不清楚：

import java.util.Arrays; public class Solution { public int FindGreatestSumOfSubArray(int[] array) { if(array.length==0)return 0; int len = array.length; int num[] = new int [len]; int max = array[0];//0x80000000具体指最小的负数(-0), 这里用MIN_VALUE有 num[0] = max; for(int i =1;i<len;i++){ if(num[i-1]>=0){ num[i] =num[i-1]+array[i]; }else { num[i]=array[i]; } max = max>=num[i]?max:num[i]; }//for return max; } }