Java计算连续子向量的最大和

题目描述

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

我的一版的想法是，用一个sum和一个temp来比较，sum记录当前的最大和，temp记录每次相加和。

如果temp>sum，那么就改变sum的值，这样sum的值就是连续子向量的最大值。

但是第一版代码并没有完全通过。通过了示范用例，但是有一些用例还是没有通过：

public class Solution { public int FindGreatestSumOfSubArray(int[] array) { int sum=array[0],temp=0; for(int j=0;j<array.length;j++){ temp+=array[j]; if(temp>sum){ sum=temp; } } return sum; } }

分析没有通过的用例：

测试用例: [1,-2,3,10,-4,7,2,-5] 对应输出应该为: 18 你的输出为: 17

为什么会出现这个情况呢？

1，-2，3，……

其实前面这个1是应该不要的。这个1和-2的和 -1 就是造成我的结果为17的原因。

因此我觉得要多加一个判断： arr[i]>0;arr[i+1]<0，需要判断这个负数对arr[i]造成的影响到底有没有抵消arr[i]的正值。如果是负值那么说明这个正数和负数统统都不能要了。把temp置0，重新开始找。

最后AC的代码为

public class Solution { public int FindGreatestSumOfSubArray(int[] array) { int sum=array[0],temp=array[0]; for(int j=1;j<array.length;j++){ temp+=array[j]; if(temp>=sum){ sum=temp; }else if(temp<0){ temp=0; } } return sum; } }