首页 > 代码库 > 连续子数组最大和

连续子数组最大和

题目:如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。

思路:动态规划入门。。。。

 

  public int FindGreatestSumOfSubArray(int[] array) {
        int n=array.length;
        if(n==0) return 0;
        //从a[0]开始,可覆盖全是负数的情况
        int temp=array[0],sum=array[0];
        for(int i=1;i<n;i++){
            if(temp<=0)
                temp=array[i];
            else 
                temp+=array[i];
            if(temp>sum) 
                sum=temp;
        }
        return sum;
            
    }

 

连续子数组最大和