连续子数组的最大和C++

连续子数组的最大和

描述

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

数据范围:

1 <= n <= 2x10⁵

-100 <= a[i] <= 100

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

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

示例1

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

示例2

输入：
[2]
返回值：
2

示例3

输入：
[-10]
返回值：
-10

解法/思路

方式一

class Solution {
  public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if (array.size() == 1)return array[0];
        int max = array[0];//从某个位置开始到当前位置为止，保留的最大值
        int sum = 0;//从开始位置到当前位置为止，存下的全局最大值
        for(int i = 0;i<array.size();i  )
        {
            //到当前位置为止，如果sum为负数，那么无论array[i]为正数还是负数，加上当前元素之后，sum都会变小，所以不如将sum设置为array[i]
            if(sum<=0)
                sum = array[i];
            else//如果array[i]为正数，下一步将会被保存至max中，而如果array[i]为负数，上一次循环max已经保留下最大值，所以无需担心。
                sum  = array[i];
            if(max < sum)
                max = sum;
        }
        return max;
    }
};

方式二

动态规划，使用额外的空间。

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

  具体思路如下：

1. 遍历数组，比较 dp[i-1] array[i] 和 array[i]的大小;
2. 为了保证子数组的和最大，每次比较 sum 都取两者的最大值;
3. 用max变量记录计算过程中产生的最大的连续和dp[i]；

class Solution {
  public:
    int GetMax(int a,int b){return a>b?a:b;}
    int FindGreatestSumOfSubArray(vector<int> array) {
        vector<int> dp(array.size());
        int max = array[0];
        dp[0] = array[0];
        for(int i = 1;i < array.size(); i  )
        {
            dp[i] = GetMax(dp[i-1] array[i],array[i]);
            max = GetMax(max,dp[i]);
        }
        return max;
    }
};

方式三

动态规划，不使用额外的存储空间。

class Solution {
  public:
    int GetMax(int a,int b){return a>b?a:b;}
    int FindGreatestSumOfSubArray(vector<int> array) {
        int sum = 0;
        int max = array[0];
        for(int i = 0;i < array.size(); i  )
        {
            sum = GetMax(sum array[i],array[i]);
            max = GetMax(max,sum);
        }
        return max;
    }
};

这篇好文章是转载于：学新通技术网