动态规划（七）——子数组系列（求和问题）

最大子数组和

最大子数组和

题目要求十分简单，想让我们求解数组最大的连续子数组的和，其中数组元素有正数也有负数，我们结合动态规划思想来解决这个问题~

分析：

1、状态表示

题目要求：求解数组最大的连续子数组的和

结合这里的题目要求+经验： dp表中的dp[i]表示为以【i】位置为结尾最大子数组和~

2、状态转移方程

我们以离【i】位置最近的状态分析状态转移方程，处理dp表 既然状态表示为： 以【i】位置为结尾最大子数组和~ ，那么第i个位置肯定在子数组中，那么以【i】位置为结尾的最大子数组和长度可能为1，那么就是它本身；以【i】位置为结尾为结尾的最大子数组和长度可能大于1，那么以【i】位置为结尾的最大子数组和就等于以【i-1】位置为结尾的最大子数组和+nums【i】~取两种情况最大值就可以了~

所以状态转移方程为: dp[i] = max(nums[i],dp[i-1]+nums[i])

3、初始化

我们可以看到，状态转移方程里面有i-1，当i=0的时候显然会出现越界的情况，所以我们需要进行初始化 结合前面如果不想初始化太麻烦，我们可以多申请一些空间，我们可以多申请一个空间，并且把这个空间填写正确的数据保证不影响到后面的结果，我们求数组和不希望影响到后面的结果的话，dp【0】影响到的是dp【1】，即dp【1】=max（nums【0】，nums【0】+dp【0】），那么dp【0】应该等于 0~同时要注意下标映射关系~ 那么我们初始化结果就是 dp【0】= 0

4、填表顺序

我们这里的逻辑是从前面依次推出后面的，所以填表顺序是从前往后

5、返回结果

这里返回结果是到最大子数组和，最大子数组可能是数组中任何一个位置为结尾的，所以我们返回dp表中最大值即可~

有了前面的分析，代码实现就比较简单了~

代码实现：

//最大子数组和
class Solution
{
public:
    int maxSubArray(vector<int>& nums)
    {
        //1、创建dp表
        int n = nums.size();
        vector<int> dp(n + 1);

        //2、初始化
        dp[0] = 0;

        int ret = INT_MIN;
        //3、填表并且更新结果
        for (int i = 1; i < n + 1; i++)
        {
            //注意下标映射关系
            dp[i] = max(dp[i - 1] + nums[i - 1], nums[i - 1]);
            ret = max(ret, dp[i]);
        }

        //4、返回结果
        return ret;
    }
};

顺利通过~

小编这里还实现不多开一个空间的初始化代码，感兴趣的小伙伴可以看一看~

class Solution
{
public:
    int maxSubArray(vector<int>& nums)
    {
        //1、创建dp表
        int n = nums.size();
        vector<int> dp(n);

        //2、初始化
        //题目给出子数组至少包含一个元素
        //那么以0位置为结尾的最大子数组和就是它本身
        dp[0] = nums[0];

        int ret = dp[0];//ret初始化为dp[0]
        //3、填表并且更新结果
        for (int i = 1; i < n; i++)
        {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            ret = max(dp[i], ret);
        }

        //4、返回结果
        return ret;
    }
};

顺利通过~

环形子数组的最大和

环形子数组的最大和

读题其实可以发现他与前面的题目十分类似，只不过这一道题目是环形数组，那么把它看成一个线性数组最大子数组和下面两种情况~

第一种情况，我们就可以使用第一个题目的思路解决，那么如果子数组和最大是第二种情况呢？分析一下：既然是头尾是最大子数组和，那么中间就是最小子数组和，用整个数组和减去最小子数组和就是我们想要的结果~那么最小子数组和我们使用动态规划思想解决~

知道了方法，接下来我们使用动态规划思想~

分析：

1、状态表示

题目要求：求解环形数组最大的连续子数组的和

结合这里的题目要求+经验+我们的分析，创建两个dp表，一个求最大子数组和，一个求最小子数组和： dp1表中的dp1[i]表示为以【i】位置为结尾最大子数组和~ dp2表中的dp2[i]表示为以【i】位置为结尾最小子数组和~

2、状态转移方程

我们以离【i】位置最近的状态分析状态转移方程，处理dp1表 既然状态表示为： 以【i】位置为结尾最大子数组和~ ，那么第i个位置肯定在子数组中，那么以【i】位置为结尾的最大子数组和长度可能为1，那么就是它本身；以【i】位置为结尾为结尾的最大子数组和长度可能大于1，那么以【i】位置为结尾的最大子数组和就等于以【i-1】位置为结尾的最大子数组和+nums【i】~取两种情况最大值就可以了~

所以状态转移方程为: dp1[i] = max(nums[i],dp[i-1]+nums[i])

我们以离【i】位置最近的状态分析状态转移方程，处理dp2表 既然状态表示为：以【i】位置为结尾最小子数组和~ ，那么第i个位置肯定在子数组中，那么以【i】位置为结尾的最小子数组和长度可能为1，那么就是它本身；以【i】位置为结尾为结尾的最小子数组和长度可能大于1，那么以【i】位置为结尾的最小子数组和就等于以【i-1】位置为结尾的最小子数组和+nums【i】~取两种情况最小值就可以了~

所以状态转移方程为: dp2[i] = min(nums[i],dp[i-1]+nums[i])

3、初始化

我们可以看到，状态转移方程里面有i-1，当i=0的时候显然会出现越界的情况，所以我们需要进行初始化 结合前面如果不想初始化太麻烦，我们可以多申请一些空间，我们可以多申请一个空间，并且把这个空间填写正确的数据保证不影响到后面的结果，我们求数组和不希望影响到后面的结果的话，dp1【0】影响到的是dp1【1】，即dp1【1】=max（nums【0】，nums【0】+dp1【0】），那么dp1【0】应该等于 0；dp2【0】影响到的是dp2【1】，即dp2【1】=min（nums【0】，nums【0】+dp2【0】），那么dp2【0】应该等于 0~同时要注意下标映射关系~ 那么我们初始化结果就是 dp1【0】= 0 ；dp2【0】= 0

4、填表顺序

我们这里的逻辑是从前面依次推出后面的，所以填表顺序是从前往后,两个dp表一起填

5、返回结果

这里返回结果是到最大子数组和，最大子数组可能是情况1，也可能是情况2，情况1的最大子数组和是dp1表中最大值；情况2的最大子数组和是整个数组和减去最小子数组和~ 返回两种情况的最大值~ 注意：如果整个数组全部是负数，情况2计算结果为0，情况1计算结果为最大的负数，题目要求子数组至少包含一个元素，所以情况1的计算结果才是正确的，进行结果返回的时候需要先判断再返回~

代码实现：

//环形子数组的最大和
class Solution
{
public:
    int maxSubarraySumCircular(vector<int>& nums)
    {
        //1、创建dp表
        int n = nums.size();
        vector<int> dp1(n + 1);//求解最大子数组和dp表
        vector<int> dp2(n + 1);//求解最小子数组和dp表

        //2、初始化
        dp1[0] = 0, dp2[0] = 0;

        //3、填表并且更新最大子数组和以及最小子数组和
        int Max_subarr_sum = INT_MIN;
        int Min_subarr_sum = INT_MAX;
        int Sum_arr = 0;
        for (int i = 1; i < n + 1; i++)
        {
            //注意下标映射关系
            dp1[i] = max(dp1[i - 1] + nums[i - 1], nums[i - 1]);
            Max_subarr_sum = max(dp1[i], Max_subarr_sum);

            dp2[i] = min(dp2[i - 1] + nums[i - 1], nums[i - 1]);
            Min_subarr_sum = min(dp2[i], Min_subarr_sum);

            Sum_arr += nums[i - 1];//统计整个数组和
        }
        //4、返回结果
        //返回两种情况最大值

        //err——全部为负数是错误的
        //return max(Sum_arr-Min_subarr_sum,Max_subarr_sum);

        //正确返回：先判断再返回
        return Sum_arr == Min_subarr_sum ? Max_subarr_sum : max(Sum_arr - Min_subarr_sum, Max_subarr_sum);

    }
};