最大子数组和问题,花式七种解法,妥妥征服一般大厂面试官


给一个一维数组,有正数也有负数,求最大子数组和是多少。

这是《编程珠玑》第八章探讨的一个主要问题,也是平时刷题和各大厂面试的常客。

作为这么经典的一个问题,要是老生常谈,那就没什么意义了,这里为大家带来七种解法,其中更有一个最优复杂度的线性算法,博主在各大厂面试的时候,碰到的面试官也非常惊讶有这么一个解法的存在。自然问到这个问题的面试,都理所当然的过了。(本博客代码不会考虑溢出等工程问题)。

本博客将包括以下七种解法的代码和讲解:

1:基于暴力枚举的三次方算法。

2:两种用动态规划稍加处理的平方算法。

3:一种基于分治算法的递归算法,复杂度为O(n*logn),以及动态规划优化后的线性时间复杂度解法。

4:两种线性复杂度算法,基于动态规划的扫描算法以及将最大子段和转化为求差的两种解法。

通过1到2的优化,会讲述如何运用动态规划的一些小技巧,3会谈到递归分治算法,4会重点讲述动态规划和一个有思维小技巧的算法。如果面试碰到这个问题,从浅入深,从以上角度把这个问题分析一遍,瞬间就能表现出和临时抱佛脚的人的差距,足够折服一般的面试官了,不出意外,此面必过。

当然无论何时,学习和感悟,永远是第一位,过面试,只是附属品。

祝大家在漫长的学习旅途中,不仅仅内功越来越深厚,现实中的面试和工作,也能披荆斩棘。

好啦,进入正题,我们就先从最基础的解法开始:

公式说明:sum(i,j)代表nums[i]一直加到nums[j],包含端点。

解法一:暴力解法

这个解法比较容易理解,不是要求最大子段和嘛,那我把所有的子数组都枚举出来求和,找个最大的就好了,复杂度O(n^3),代码如下:

int force(){

    int ans = 0;

    for (int i = 0; i < nums.size(); ++i){
        for (int j = i; j < nums.size(); ++j){
            int sum = 0;
            for (int k = i; k <= j; ++k){
                sum += nums[k];
            }
            ans = max(ans, sum);
        }
    }

    return ans;
}

解法二:带有初步动态规划优化的解法:

我们在枚举子数组求和的时候,子数组1,2..j和1,2..j-1就只差一个nums[j],那么我们在求和的时候,就没必要每次都从1开始到j都加一遍,只需要在上一次j-1和的基础上再加nums[j]就可以了,这样就优化掉了最里面的循环,复杂度变为O(n^2)

int dp1(){

    int ans = 0;

    for (int i = 0; i < nums.size(); ++i){
        int sum = 0;
        for (int j = i; j < nums.size(); ++j){
            sum += nums[j];
            ans = max(ans, sum);
        }
    }

    return ans;
}

解法三:保存数组前i项和:

我们要求某个子数组i-j的和,其实可以转化为前j项和减去前i-1项和,sum(i,j) = sum(0,j) - sum(0,i -1),那么我们把前i项和放在一个数组里,用额外的空间存储起来就可以在O(1)的时间求出某个子数组和,用空间换取时间,空间复杂度O(n),时间复杂度O(n ^ 2),代码如下:

int cachePreSum(){
    int ans = 0;
    int cache[1000];

    cache[0] = 0;
    for (int i = 1; i <= nums.size(); ++i){
        cache[i] = cache[i - 1] + nums[i - 1];
    }

    for (int i = 0; i < nums.size(); ++i){
        int sum = 0;
        for (int j = i; j < nums.size(); ++j){
            sum = cache[j + 1] - cache[i];
            ans = max(ans, sum);
        }
    }

    return ans;
}

解法四:分治算法

这个解法比较少见,其基本思想是,一个数组的最大子段和只有三种情况:

情况一:最大子数组出现在左半部分:

情况二:最大子数组出现在右半部分:

情况三:最大子数组一部分在左半部分的最右端,另一部分在右半部分的最左端。

0 0 0 1 1 1 1 0 0 0
如上表标为1的部分。

那么分析情况三:在左半部分的最右端的那部分,一定是从最右端连读到左边所有数和最大的那部分。在右半部分最左端的,一定是从最左端连续到右边所有数和最大的部分。由于分支的递归过程会把所有区间段都分解到只剩一个数,然后在递归反回的时候再合并两个数的区间,由此向上不断合并。那么递归过程其实处理情况3就好了。复杂度为O(n * logn)。

代码如下:

int DivideConquer(int l, int r){
    //没有元素是反回0
    if (l > r){
        return 0;
    }
    //只有一个元素,反回和0比较大的哪个
    if (l == r){
        return max(0, nums[l]);
    }

    int m = (l + r) / 2;

    int sum = 0;
    int leftMax = sum = 0;
    //计算左边的最大字段和
    for (int i = m; i >= 0; i--){
        sum += nums[i];
        leftMax = max(leftMax, sum);
    }

    //计算右边的最大字段和
    int rightMax = sum = 0;
    for (int i = m + 1; i <= r; ++i){
        sum += nums[i];
        rightMax = max(sum, rightMax);
    }

    //递归计算最大部分
    return max(max(leftMax + rightMax, DivideConquer(l, m)), DivideConquer(m + 1, r));
}

解法五:如果细心会发现,解法五中递归的时候会有重复计算,保存下中间过程便可以把时间复杂度优化到线性时间,了解记忆化搜索和动态规划关系的同学,不难写出代码来。

代码如下:

int cache5[1000][1000];
需要如下初始化:
for (int i = 0; i <= nums.size(); ++i){
    for (int j = 0; j <= nums.size(); ++j){
        cache5[i][j] = INT_MAX;
    }
}
int DivideConquerWithCatch(int l, int r){
    //没有元素是反回0
    if (l > r){
        return 0;
    }
    //只有一个元素,反回和0比较大的哪个
    if (l == r){
        return max(0, nums[l]);
    }

    if (cache5[l][r] != INT_MAX){
        return cache5[l][r];
    }
 
    int m = (l + r) / 2;
 
    int sum = 0;
    int leftMax = sum = 0;
    //计算左边的最大字段和
    for (int i = m; i >= 0; i--){
        sum += nums[i];
        leftMax = max(leftMax, sum);
    }
 
    //计算右边的最大字段和
    int rightMax = sum = 0;
    for (int i = m + 1; i <= r; ++i){
        sum += nums[i];
        rightMax = max(sum, rightMax);
    }
 
    //递归计算最大部分
    int ans = max(max(leftMax + rightMax, DivideConquer(l, m)), DivideConquer(m + 1, r));
    cache5[l][r] = ans;

    return ans;
}

解法六:基于动态规划的扫描算法:

想想啊,对于以j为结尾这个位置来说,最大子段有两种可能,一种可能是最大子段结尾就是j,一种可能是最大子段结尾不是j。

对于最大子段结尾就是j这种情况:

maxsum = max(sum(i, j-1)+ nums[j], 0);

意思是,从i开始的某个数,一直加到j

对于最大子段结尾不是j的情况:

maxsum 就是 在计算j-1的最大值。

代码如下:

int dp2(){

    int ans = 0, sum = 0;
    for (int i = 0; i < nums.size(); ++i){
        sum = max(sum + nums[i], 0);
        ans = max(ans, sum);
    }

    return ans;
}

解法七:和转化为差的动态规划解法:

这个解法极其少见,博主面试很多大厂的时候,面试官都表示没见过这个解法,然后博主被问到这个问题的面试都毫无压力的过了。

考虑这么个情况,就是以j结尾的子段,最大子段和其实是sum(0,j) - min(sum(0, i)) i属于[0,j-1]。

换句话说,当前子段0到j的和最大子段和,等于0到j的和,减去0到j之前连续子段和的最小值。

代码如下:
int solve6(){
    if (nums.size() == 0) {
        return 0;
    }

    int ans = 0x80000000;
    int preMin = 0, curSum = 0, preSum = 0;
    for (int i = 0; i < nums.size(); ++i){
        curSum += nums[i];
        ans = max(ans, curSum - preMin);
        preSum += nums[i];
        preMin = min(preMin, preSum);
    }

    return ans;
}


附上完整代码:

include <iostream>

include <cstdio>

include <vector>

include <algorithm>

 
using namespace std;
 
vector<int> nums;
 
int force();
int dp1();
int cachePreSum();
int DivideConquer(int l, int r);
int DivideConquerWithCatch(int l, int r);
int dp2();
int solve6();

int cache5[1000][1000];
 
int main(){
 
    freopen("in.txt", "r", stdin);
 
    int num;
    while (scanf("%d", &num) != EOF){
        nums.push_back(num);
    }
 
    cout << "1--" << force() << endl;
    cout << "2--" << dp1() << endl;
    cout << "3--" << cachePreSum() << endl;
    cout << "4--" << DivideConquer(0, nums.size() - 1) << endl;

    for (int i = 0; i <= nums.size(); ++i){
        for (int j = 0; j <= nums.size(); ++j){
            cache5[i][j] = INT_MAX;
        }
    }
    cout << "5--" << DivideConquerWithCatch(0, nums.size() - 1) << endl;
    cout << "6--" << dp2() << endl;
    cout << "7--" << solve6() << endl;
    return 0;
}
 
int force(){
 
    int ans = 0;
 
    for (int i = 0; i < nums.size(); ++i){
        for (int j = i; j < nums.size(); ++j){
            int sum = 0;
            for (int k = i; k <= j; ++k){
                sum += nums[k];
            }
            ans = max(ans, sum);
        }
    }
 
    return ans;
}
 
int dp1(){
 
    int ans = 0;
 
    for (int i = 0; i < nums.size(); ++i){
        int sum = 0;
        for (int j = i; j < nums.size(); ++j){
            sum += nums[j];
            ans = max(ans, sum);
        }
    }
 
    return ans;
}
 
int cachePreSum(){
    int ans = 0;
    int cache[1000];
 
    cache[0] = 0;
    for (int i = 1; i <= nums.size(); ++i){
        cache[i] = cache[i - 1] + nums[i - 1];
    }
 
    for (int i = 0; i < nums.size(); ++i){
        int sum = 0;
        for (int j = i; j < nums.size(); ++j){
            sum = cache[j + 1] - cache[i];
            ans = max(ans, sum);
        }
    }
 
    return ans;
}
 
int DivideConquer(int l, int r){
    //没有元素是反回0
    if (l > r){
        return 0;
    }
    //只有一个元素,反回和0比较大的哪个
    if (l == r){
        return max(0, nums[l]);
    }
 
    int m = (l + r) / 2;
 
    int sum = 0;
    int leftMax = sum = 0;
    //计算左边的最大字段和
    for (int i = m; i >= 0; i--){
        sum += nums[i];
        leftMax = max(leftMax, sum);
    }
 
    //计算右边的最大字段和
    int rightMax = sum = 0;
    for (int i = m + 1; i <= r; ++i){
        sum += nums[i];
        rightMax = max(sum, rightMax);
    }
 
    //递归计算最大部分
    return max(max(leftMax + rightMax, DivideConquer(l, m)), DivideConquer(m + 1, r));
}


int DivideConquerWithCatch(int l, int r){
    //没有元素是反回0
    if (l > r){
        return 0;
    }
    //只有一个元素,反回和0比较大的哪个
    if (l == r){
        return max(0, nums[l]);
    }

    if (cache5[l][r] != INT_MAX){
        return cache5[l][r];
    }
 
    int m = (l + r) / 2;
 
    int sum = 0;
    int leftMax = sum = 0;
    //计算左边的最大字段和
    for (int i = m; i >= 0; i--){
        sum += nums[i];
        leftMax = max(leftMax, sum);
    }
 
    //计算右边的最大字段和
    int rightMax = sum = 0;
    for (int i = m + 1; i <= r; ++i){
        sum += nums[i];
        rightMax = max(sum, rightMax);
    }
 
    //递归计算最大部分
    int ans = max(max(leftMax + rightMax, DivideConquer(l, m)), DivideConquer(m + 1, r));
    cache5[l][r] = ans;

    return ans;
}
 
int dp2(){
 
    int ans = 0, sum = 0;
    for (int i = 0; i < nums.size(); ++i){
        sum = max(sum + nums[i], 0);
        ans = max(ans, sum);
    }
 
    return ans;
}
 
int solve6(){
    if (nums.size() == 0) {
        return 0;
    }
 
    int ans = 0x80000000;
    int preMin = 0, curSum = 0, preSum = 0;
    for (int i = 0; i < nums.size(); ++i){
        curSum += nums[i];
        ans = max(ans, curSum - preMin);
        preSum += nums[i];
        preMin = min(preMin, preSum);
    }
 
    return ans;
}


本文内容来自:《编程珠玑》代码之路11:最大子数组和问题,花式七种解法

0 个评论

要回复文章请先登录注册

返回顶部