30.连续子数组的最大和

一、题目描述

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

二、思路

首先，我们会想到用两个数来辅助存储当前的最大和，定义两个变量res和sum，res用来记录当前的最大和，sum用来记录当前的和，如果sum大于res，则更新res。这一步想好之后，接下来就是遍历数组，我们最容易想到的就是使用双层循环来遍历数组，以便找到从任意位置开始的连续子数组的最大和，但是，如果仔细想想，其实，我们只对数组遍历一次，也是能够找到连续子数组的最大和的，下面是两种方法的代码实现。

方法一：使用双层循环，时间复杂度O(n^2)

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

方法二：单层循环，在方法一中，如果数组第i个元素为负数，那么我们其实是没有必要进行i元素以后的遍历的，因为，负数总会让和变小，既然要变小，我们为什么还要这一次遍历呢？所以就有下面的改进方法。

/**
*改进版，遍历一次数组即可,时间复杂度O(n)。
*用两个变量来进行记录，一个用于加和，一个用于记录最大和。
**/
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if (array.length ==  || array == null)
            return ;
        int res = array[];
        int sum = ;
        for (int i = ; i < array.length; i++){
            if (sum < ){
                sum = array[i];//因为加一个负数肯定会使结果小于array[i]，所以直接舍去负数
            } else {
                 sum += array[i];
            }
            if (sum > res)
                res = sum;
        }
        return res;
    }
}
           

该题目的变形：求使出现最大和的子数组；

思路：用两个标签分别记录子数组开始和结束的位置，如果使用for双层循环的话，当出现新的最大值时，分别记录i和j的值，下面是另一种循环求解：

/*
     * 1.找出出现最大连续和的子数组
     * 当数组有正有负时，i=0遍历数组，从大于0的那个元素开始，记录此时的下标为shart（最大子数组起始下标），从start开始遍历剩下的元素，若元素和num大于max的值则更新max，
     * 且将此时的下标赋值给end（最大子数组终止下标），当num小于0则说明后面出现的（如果出现）最大子数组不可能包含这些元素，所以退出内层循环，继续外层循环，找下一个大于
     * 0的数组元素，且外层循环的i变量此时变为temp+1，继续下面的循环。注意内层循环当temp>=length时，说明内层循环已经把所有数组元素都遍历结束，所以外层循环可以直接break。
     */
    public static ArrayList<Integer> findGreatestSumArrayOfSubArray(int arr[]) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        int i = ;
        int temp = ;
        int num = ;
        int max = ;
        int start = ;
        int end = ;
        int flag = ;//用来判断数组中是否全为负，如果flag = arr.length,则全为负数
        while (i < arr.length){ //第一层循环，从大于零的元素位置开始，并记录开始下标，
            if (arr[i] > ){
                temp = i;
                start = i;
                while (temp < arr.length){ //第二层循环，用temp做临时变量，找最大值，并记录最大值结束下标
                    num += arr[temp];
                    if (num < ){
                        num = ;
                        i = temp + ;
                        break;
                    }
                    if (num > max){
                        max = num;
                        end = temp;
                    }
                    temp++;
                }
                if(temp >= arr.length) //避免在外层循环中陷入死循环，因为此时i不一定等于数组长度，i值不增，外层循环则停不下来。
                    break;
            }
            else {
                i++;
                flag++;
            }
        }
        if (flag == arr.length) //如果元素全为负，则输出空数组
            return list;
        else {
            for (int j = start; j<= end; j++)
                list.add(arr[j]);
        }
        return list;
    }