数据结构和算法之最大子数组之和五种优化(O(n^3)->O(n))

文一西路代码狗 2020-07-17

530

1、背景介绍

2、蛮力枚举法(O(n^3))

3、优化的蛮力枚举法(O(n^2))

4、分而治之算法(O(nlogn))

5、一般动态规划算法(O(n))

6、优化的动态规划(O(n))

一、背景介绍

所谓最大子数组问题（maximum subarray problem），指的是给定一个数组Arr，计算Arr的非空连续子数组最大值。比如，数组 Arr = {133, 121, -12, 14, 534, -23, 87, -87, 81, 41}，最大子数组应为[13 121 -12 14 34 -23 87 -87 81 41], 其和为269。

对于一组数简单的分为三种情况，如果Arr中的元素全部为正，则最大子数组就是它本身；如果Arr中的元素全部为负，则最大子数组就是第一个元素组成的数组；另外Arr中的元素既有正数，又有负数，则该如何求解呢？本文将介绍该问题的几种算法，并以不断优化的方式分析其时间复杂度。

二、蛮力枚举法(O(n^3))

所谓蛮力枚举法，就是依次以数组中每个元素为子数组的第一个元素进行枚举分别有一个元素、两个元素、三个元素.....的各个子数组，分别计算每个子数组之和，然后再从Arr中以第二个元素重复这样的过程。最后求取所有之和中的最大值即为Arr的最大子数组之和。

为了更加便于理解，下面给出图示：(以数组 Arr = {133, 121, -12, 14, 534, -23, 87, -87, 81, 41}为例)

以13开头的子数组有：
13 
13 121 
13 121 -12 
13 121 -12 14 
13 121 -12 14 34 
13 121 -12 14 34 -23 
13 121 -12 14 34 -23 87 
13 121 -12 14 34 -23 87 -87 
13 121 -12 14 34 -23 87 -87 81 
13 121 -12 14 34 -23 87 -87 81 41 
以121开头的子数组有：
121   
121 -12 
121 -12 14 
121 -12 14 34 
121 -12 14 34 -23 
121 -12 14 34 -23 87 
121 -12 14 34 -23 87 -87 
121 -12 14 34 -23 87 -87 81 
121 -12 14 34 -23 87 -87 81 41


//忽略部分示例


以41开头的子数组有：
子数组有：41

Java代码实现如下：

     /**
     * 最大子数组问题算法（蛮力法 O(n^3)）
     */
    private static void getSumOfSubArray01(int array[]) {
        int n = array.length;
        int cuSum, maxSum = Integer.MIN_VALUE, k, i, j;
        for (i = 0; i < n; i++) {
            for (j = i; j < n; j++) {
                cuSum = 0;
                System.out.print("子数组：");
                //k j分别为子数组的起止下标
                for (k = i; k <= j; k++) {
                    cuSum = cuSum + array[k];
                    //枚举所有的子数组
                    System.out.print(array[k] + " ");
                }
                System.out.println();
                if (cuSum > maxSum) {
                    maxSum = cuSum;
                }
            }
        }
        System.out.println("最大子数组之和为：" + maxSum);
    }

蛮力枚举实现思想非常的简单，就算是没有受过任何算法训练的程序员来说，根据题意应该也都能实现，但是蛮力枚举时间复杂度实在是太高，性能一般，接下来给出一种优化方案。

三、优化的蛮力枚举法(O(n^2))

普通的蛮力枚举之所以时间复杂度这么高，就是存在大量的重复计算，每求一个子数组之和就对所有涉及到的元素都访问一遍，所以从这个方面入手先对最内层for循环进行优化。

最内层for循环其实完全不必每次求以k为起点的子数组的时候之前的访问过的元素又都重新计算一遍，只需用一个临时变量进行存储之前相同元素计算过的值就行了。

优化的Java代码实现如下：

    /**
     * 最大子数组问题算法（优化的蛮力法）（重复利用已经计算的子数组和，相比较方法一,时间复杂度为：O（n^2））
     */
    private static void getSumOfSubArray02(int array[]) {
        int n = array.length;
        int cuSum, maxSum = Integer.MIN_VALUE, i, j;
        for (i = 0; i < n; i++) {
            for (j = i; j < n; j++) {
                cuSum = 0;
                cuSum = cuSum + array[j];
                if (cuSum > maxSum) {
                    maxSum = cuSum;
                }
            }
        }
        System.out.println("最大子数组之和为：" + maxSum);
    }

这种算法结果时间复杂度为O(n^2)，相对于普通蛮力枚举法有所提升，不过对于平方阶的时间复杂度我们还是不能接受，下面再进一步优化。

四、分而治之算法(O(nlogn))

首先介绍下分而治之算法思想：在计算机科学中，分治法是基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。【百度百科】

从上面这段话可以提炼出几个重要信息：①、原问题的求解依赖于子问题的解。②、子问题通过递归拆分最终能够求解。③、所有子问题的解进行合并即是原问题的解。

在本题中既然求的是Arr的最大子数组之和，我们不妨把Arr拆分成两个小数组，分别为Arr1，Arr2，如果那么Arr的最大子数组之和要么出现在Arr1中，要么出现在Arr2中，要么横跨Arr1和Arr2，对于Arr1我们利用同样的方式进行二分，拆分之后再不断地二分...... 最终以Arr1为例最左边的两个元素为133和121，二分拆成[133]和[121]，然后再合并子问题解，数组[133]和数组[121]和数组[133,121]进行比较谁的子数组值最大，依次字底向上进行合并即可得到原问题Arr的最大子数组之和。

为了更加便于理解，下面给出图示：

自顶向下拆分：

自底向上合并：

总体图示：

Java代码实现如下：

    /**
     * @Date: 2020-03-24
     * @Description: 最大子数组问题算法(分治法 、 无左右下标)
     */
    public static int maxSubArraySort(int a[], int low, int high) {
        if (low > high) {
            return 0;
        }
        if (low == high) {
            return a[0];
        }
        int S_Left = 0, S_Right = 0, S_Cross_Left_Right = 0;
        //while (low < high) {
        int i = low;
        int j = high;
        int mid = (i + j) / 2;
        S_Left = maxSubArraySort(a, i, mid);
        S_Right = maxSubArraySort(a, mid + 1, j);
        S_Cross_Left_Right = CrossLeftAndRight(a, i, mid, j);
        //}
        return maxInThreeNum(S_Left, S_Right, S_Cross_Left_Right);
    }


    public static int CrossLeftAndRight(int a[], int low, int mid, int high) {
        int Sub_Left_Sum = Integer.MIN_VALUE;
        int Sub_Left_Sum_Tem = 0;
        for (int i = mid; i >= low; i--) {
            Sub_Left_Sum_Tem += a[i];
            if (Sub_Left_Sum_Tem > Sub_Left_Sum) {
                Sub_Left_Sum = Sub_Left_Sum_Tem;
            }
        }
        int Sub_Right_Sum = Integer.MIN_VALUE;
        int Sub_Right_Sum_Tem = 0;
        for (int i = mid + 1; i <= high; i++) {
            Sub_Right_Sum_Tem += a[i];
            if (Sub_Right_Sum_Tem > Sub_Right_Sum) {
                Sub_Right_Sum = Sub_Right_Sum_Tem;
            }
        }
        return Sub_Left_Sum + Sub_Right_Sum;
    }


   public static int maxInThreeNum(int S_Left, int S_Right, int S_Cross_Left_Right) {
        return (S_Left > S_Right ? (S_Left > S_Cross_Left_Right ? S_Left : S_Cross_Left_Right) : (S_Right > S_Cross_Left_Right ?
                S_Right : S_Cross_Left_Right));
    }

至于时间复杂度分析，自顶向下进行分解时间复杂度是logn的，然后自底向上合并是线性时间复杂度O(n)的，所以总体的时间复杂度就为O(nlogn)。

不过对于这个问题来说，使用分治算法进行求解合并的过程中会发现还是有重复元素访问的过程，导致我们猜想是否能够所有元素我只访问一次就能求解，因为解决一组数问题，至少你需要把所有数访问一遍才能进行后续操作，否则是没有意义的，所以针对此目标还是有方法进行进一步优化时间复杂度的。

五、一般动态规划算法(O(n))

对于动规算法来讲，基本概念介绍限于篇幅原因这里不再赘述，如果初次接触也没关系，这里会介绍其算法分析特点，抓住了关键点就不难理解。

适用于动态规划的问题一般都满足以下条件：①、大多是决策性求解最优解问题。②、大问题的最优解依赖于小问题的最优解(最优子结构性质)。三、子问题最优解中存在重叠性(重叠子问题)。

然后介绍一般性的动态规划通常包括四步骤：

分析原问题(最优子结构和重叠子问题)
找出递推关系式
自底向上计算
追踪最优过程

对于最大子数组之和问题首先求解的是最大子数组，一个数组的子数组会有很多个，但是最大子数组之和只有一个(最大子数组可能存在多个)，满足①。

对于本文章给出的数组例子，元素一共有十个，求解十个元素的最大子数组之和一定依赖于求解九个元素最大子数组之和、八个元素最大子数组之和......因为如果我们连九个元素最大子数组之和、八个元素最大子数组......之和都不知道，那么根本无从谈起求解十个元素最大子数组之和。满足②。

基于上面所述，大问题的求解依赖于小规模问题的求解，换言之，比如我们求解三个元素的最大子数组之和和求解四个元素的最大子数组之和一定存在重叠部分，也就是说三个元素的最大子数组之在求解四个元素的最大子数组之和的过程中一定会出现。满足③。

如果利用动态规划解本题该方法时间复杂度为：o(n),但是额外使用了两个数组空间，其空间复杂度为：o(n)。

* 解题思路：对于一个数组，求最大子数组之和，可以分为三种情况：

* 最大子数组以array[n-1]作为最后一个元素：

* 1：array[n-1]自己构成最大的子数组

* 2：包含array[n-1]的最大子数组，即以array[n-1]结尾，我们用ev[n-1]表示

* 3：不包含array[n-1]的最大子数组，那么也就是求array[0]...array[n-1]的子数组，可以转化为求array[0]...array[n-2]的最大子数组

由以上可知，递推关系式为：curr[n-1]=max{array[n-1],ev[n-1],curr[n-1]}

curr[n-1]表示为：array[0]...array[n-1]的最大子数组之和

Java代码实现如下：

private static void getSumOfSubArray03(int array[]) {
        int n = array.length;
        int ev[] = new int[n];
        int curr[] = new int[n];
        int rec[] = new int[n];
        //初始化
        ev[0] = curr[0] = array[0];
        ev[n - 1] = curr[n - 1] = array[n - 1];
        for (int i = 1; i < n; i++) {
            //Ent[i]是数组array[i]前i个数最大子数组之和
            ev[i] = max(ev[i - 1] + array[i], array[i]);
            if (ev[i - 1] > 0) {
                rec[i] = rec[i - 1];
            } else if (ev[i - 1] <= 0) {
                rec[i] = i;
            }
            curr[i] = max(ev[i], curr[i - 1]);
        }
        System.out.println("最大子数组之和为：" + curr[n - 1]);
        getRec(rec, ev);
    }


    private static void getRec(int rec[], int end[]) {
        int S = end[end.length - 1];
        int l = 0, r = 0;
        for (int i = end.length - 1; i > 0; i--) {
            if (S < end[i]) {
                S = end[i];
                r = i;
                l = rec[i];
            }
        }
        System.out.println("起止下标为：" + l + "-" + r);
    }

这种方法是为了贴近动态规划解法的一般步骤按部就班进行实现。

ev[i]是数组array中以array[i]为结尾的最大子数组之和。

curr[n-1]表示为：array[0]...array[n-1]的最大子数组之和。

rec用来记录下标，getRec方法用于追踪最优解的起止下标。

时机问题中可能并没有一定按照一般步骤按部就班进行实现那么机械，所以有了下面这种稍微优化了一下的方式：

private static void getSumOfSubArray05(int array[]) {
        int n = array.length;
        int ev[] = new int[n];
        //初始化
        ev[0] = array[0];
        ev[n - 1] = array[n - 1];
        for (int i = 1; i < n; i++) {
            ev[i] = max(ev[i - 1] + array[i], array[i]);
        }
        System.out.println("最大子数组之和为：" + Arrays.stream(ev).max().getAsInt());
    }

然后这种优化可以说挺好的了，但是再仔细分析会发现求解最优解最终我们需要的只是最终的一个最优的结果值，没必要把计算过程中的最优解全部都记录下来，所以有了进一步优化的空间。

六、优化的动态规划(O(n))

为了进一步降低空间复杂度，我们可以定义两个变量用来保存数组中的最终最优解。

private static void getSumOfSubArray04(int array[]) {
        int n = array.length;
        int ev = array[0]; 
        int curr = array[0];
        for (int i = 1; i < n; i++) {
            ev = max(ev + array[i], array[i]);
            curr = max(ev, curr);
        }
        System.out.println("最大子数组之和为：" + curr);
    }

至此，最大子数组问题就分析完了。

可以看到每种算法实现，都有各自的优缺点。对于暴力枚举，想法最简单，但是算法效率不高。分治算法运行效率高，但是其治的过程设计比较麻烦。动态规划法想法巧妙，运行效率也高，但是普适性不高，不过最重要的还是能够领会算法的设计思想。

数据库

文章转载自文一西路代码狗，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

数据结构和算法 之 最大子数组之和五种优化(O(n^3)->O(n))

评论

数据结构和算法之最大子数组之和五种优化(O(n^3)->O(n))