本文共 1429 字，大约阅读时间需要 4 分钟。

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

思路：如何找出最大子序列

方法1：根据题目的特性来找解决方法，特殊的，对于全为非正的数组，最大子序列不能是0，而是其中的最大的元素，所以先遍历一遍数组找出最大值maxNum，如果maxNum<=0则直接返回这个manNum作为最大值；如果最大值为正数，那么必定存在某个连续的子序列和最大，此时设置两个变量，sumMax用来记录当前最大子序列的和，temp用来记录当前连续几个元素的和，通过temp的情况开判断是否要把这部分的元素加到最大子序列上面去，如果temp>sumMax,说明当前的元素加上去有益于sum，因此要将sumMax更新为temp；如果temp<0,说明当前元素以及前面的几个元素的序列和是负数，如果加到连续子序列上面只会使得和减小，因此应该抛弃前面的子序列，而从后面的元素开始重新查找最大子序列，此时将sumMax，temp恢复成为0，因为已经排除了全为负数的情况，因此必然至少有一个正数，即0一定会被正数所覆盖，因此可以将sumMax，temp恢复成为0，即这里需要提前已经排除了数组全部为非整数的情况。

//给定一个数组，有正有负，求出其中连续的一个子数组，使得他的和最大，返回最大值{1,-2,3,10,-4,7,2,-5}public class Solution {    public int FindGreatestSumOfSubArray(int[] array) {        //特殊的输入        if(array==null||array.length<=0) return 0;        int maxNum=array[0];        //如果全为负数或0则返回最大值        for(int i=1;i
   
    maxNum){                maxNum=array[i];            }        }        //表明全部元素都为负数或者0,直接用此最大值作为最大子序列和        if(maxNum<=0) return maxNum;        //一边遍历一边记录最大子数组的和        //记录当前的最大值        int sumMax=0;        //记录临时的连续数组和        int temp=0;        for(int i=0;i
    
     sumMax){            	sumMax=temp;            }else if(temp<0){                //表示此前的所有数没有加上去的必要,从之后的数开始重新计算                sumMax=0;                temp=0;            }        }        return sumMax;    }}
    
   

转载地址：http://qvzin.baihongyu.com/