连续子数组的最大和

题目描述

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

思路一

要求连续子数组的最大和，那么容易想到的方法是暴力**法：将所有的连续子数组的和求出来，然后返回最大和

时间复杂度：o(n^2)

import java.util.*;
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int len = array.length;
        //arrSum是作为外层循环的最大和
        int arrSum = Integer.MIN_VALUE;
        for(int i = 0; i < len; i++){
            //subSum是作为内层循环的最大和
            int subSum = Integer.MIN_VALUE;
            int temp = 0;
            for(int j = i; j < len; j++){
             	//注意这里不能直接用subSum来和array[i]相加
                temp = temp + array[j];//注意这里是array[j]不是array[i]
                if(temp > subSum){
                    subSum = temp;
                }
            }
            //每结束一层内循环需要和arrSum比较
            if(subSum > arrSum){
                arrSum = subSum;
            }
        }
        return arrSum;
    }
}

思路二

举例分析数组的规律，如果即将要累加某个数array[i]时，前面的累加值小于0，那么如果继续用前面的累加值的话，那么最终的和肯定是往小的趋势发展，所以当前面的累加值和小于0时，那么就将当前array[i]作为最大值（子序列的第一个）开始累加。

时间复杂度：o(n)

  public int FindGreatestSumOfSubArray(int[] array) {
       if (array.length==0 || array==null) {
             return 0;
         }
         int curSum=0;
         int greatestSum=Integer.MIN_VALUE;
         for (int i = 0; i < array.length; i++) {
             //先判断之前的累加值的大小，再进行累加当前值
             if (curSum<=0) {
                 //这里直接将当前值作为最大值，也就是新的子序列的第一个数
                 curSum=array[i]; //记录当前最大值
             }else {
                 curSum+=array[i]; //当array[i]为正数时，加上之前的最大值并更新最大值。
             }
             //累加了当前值之后再和最大和进行比较
             if (curSum>greatestSum) {
                 greatestSum=curSum; 
             }
         }
         return greatestSum;
    }

反面教材

   public int FindGreatestSumOfSubArray(int[] array) {
       int len = array.length;
       int maxSum = Integer.MIN_VALUE;
       int accSum = Integer.MIN_VALUE;

       int temp = 0;
       for(int i = 0; i < len; i++){
           //这里不能先进行累加当前值
           temp = temp + array[i];
           if(temp < accSum){
               //这里不能重置为0，而应该重置为当前值，将当前值作为新的子序列的第一个数
               accSum = 0;
               temp = 0;
           }else {
               maxSum = temp;
               accSum = temp;
           }
           if(accSum > maxSum){
               maxSum = accSum;
           }

       }

       return maxSum;
   }

思路三（动态规划算法）

如果采用自底向上的动态规划算法的话，事实上和思路二的代码是差不多的，所以把第二种思路的解法记好就可以了。

参考：《算法导论》第三版