• 每日一题:连续子数组的最大和(动态规划)


    JZ42 连续子数组的最大和

    知识点动态规划

    描述

    输入一个长度为n的整型数组array,数组中的一个或连续多个整数组成一个子数组,子数组最小长度为1。求所有子数组的和的最大值。

    数据范围:

    1 <= n <= 2*10^5

    -100 <= a[i] <= 100

    要求:时间复杂度为 O(n)O(n),空间复杂度为 O(n)O(n)

    进阶:时间复杂度为 O(n)O(n),空间复杂度为 O(1)O(1)

    示例1

    输入:[1,-2,3,10,-4,7,2,-5]
    返回值18
    说明:经分析可知,输入数组的子数组[3,10,-4,7,2]可以求得最大和为18         
    
    • 1
    • 2
    • 3

    示例2

    输入:

    输入:[2]
    返回值:2
    
    • 1
    • 2

    示例3

    输入:

    输入:[-10]
    返回值:-10
    
    • 1
    • 2

    解题思路

    方法1: 连续的子数组,即数组中从i下标到j下标(0<=i<=j<数组长度)的数据,想要获得所有的子数组和,可以通过暴力法,两次循环获得,但时间复杂度为O(n^2),效率不高。

    方法2: 动态规划,设动态规划列表 dp,dp[i] 代表以元素 array[i] 为结尾的连续子数组最大和。
    状态转移方程: dp[i] = max(dp[i-1] + array[i], array[i]);

    具体思路如下:
    1、遍历数组,比较 dp[i-1] + array[i] 和 array[i]的大小;
    2、为了保证子数组的和最大,每次比较 sum 都取两者的最大值;
    3、用max变量记录计算过程中产生的最大的连续和dp[i];

    方法3: 我们可以简化动态规划,使用一个变量sum来表示当前连续的子数组和,以及一个变量max来表示中间出现的最大的和。

    代码实现

    方法1:暴力法,时间复杂度O(n^2),空间复杂度O(1)

    class Solution {
    public:
        int FindGreatestSumOfSubArray(vector<int> array) {
            int Max = array[0];
            int sum = 0;
            for(int i = 0; i < array.size(); ++i)
            {
                // 每开启新的循环,需要把sum归零
                sum = 0;
                for(int j = i; j < array.size(); ++j)
                {
                    // 这里是求从i到j的数值和
                    sum += array[j];
                    // 每次比较,保存出现的最大值
                    Max = max(Max, sum);
                }
            }
            return Max;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    方法2:动态规划,时间复杂度O(n),空间复杂度O(n)

    class Solution {
    public:
        int FindGreatestSumOfSubArray(vector<int> array) {
            int* dp = new int[array.size()];
            int Max = array[0];
            dp[0] = array[0];
            for(int i = 1; i < array.size(); ++i)
            {
                // 动态规划,状态转移方程,确定dp[i]的最大值
                dp[i] = max(dp[i - 1] + array[i], array[i]);
                // 每次比较,保存出现的最大值
                Max = max(Max, dp[i]);
            }
            return Max;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    方法3:优化动态规划,时间复杂度O(n),空间复杂度O(1)

    class Solution {
    public:
        int FindGreatestSumOfSubArray(vector<int> array) {
            if(array.empty())
                return 0;
            int Max = array[0];
            int sum = array[0];
            for(int i = 1; i < array.size(); ++i)
            {
                // 优化动态规划,确定sum的最大值
                sum = max(sum + array[i], array[i]);
                // 每次比较,保存出现的最大值
                Max = max(Max, sum);
            }
            return Max;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    另一种写法:不用max的写法,就是用 if语句代替

    /*
    算法时间复杂度 O(n)
    用cur记录累计值,maxSum记录和最大
    基于思想:对于一个数A,若是A的左边累计数非负,那么加上A能使得值不小于A,认为累计值对
              整体和是有贡献的。如果前几项累计值负数,则认为有害于总和,cur记录当前值。
    此时 若和大于maxSum 则用maxSum记录下来
    */
    class Solution {
    public:
        int FindGreatestSumOfSubArray(vector<int> array) {
            if(array.empty())
                return 0;
            int maxSum = array[0];
            int cur = array[0];
            for(int i = 1; i < array.size(); ++i)
            {
                if(cur >= 0)
                    cur += array[i];
                else
                    cur = array[i];
            
                if(cur > maxSum)
                    maxSum = cur;
            }
            return maxSum;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
  • 相关阅读:
    开发板笔记本电脑手机之间互相访问-端口转发
    Python|OpenCV-访问并修改图片像素值,鉴别彩色和灰色图像(6)
    ip组成及解决
    Hadoop大数据平台搭建(超详细步骤)
    蒜头君破案(stl—set,stl—vector练习)
    This dependency was not found: vxe-table/lib/vxe-table in ./src/main.js
    保姆式教程:MAC安装Android studio(包括安装JDK,Android SDK),解决gradle下载慢的问题
    什么是DOM和DOM操作
    从零开始手写一个Transformer
    Oracle/PLSQL: Round Function (with numbers)
  • 原文地址:https://blog.csdn.net/lirendada/article/details/126053094