一起学习交流~

环形子数组的最大和-dp解

算法 laomuji 8个月前 (01-30) 356次浏览 已收录 0个评论

目录

题目

给定一个由整数数组 A 表示的环形数组 C,求 C 的非空子数组的最大可能和。
在此处,环形数组意味着数组的末端将会与开头相连呈环状。(形式上,当0 <= i < A.length 时 C[i] = A[i],且当 i >= 0 时 C[i+A.length] = C[i])
此外,子数组最多只能包含固定缓冲区 A 中的每个元素一次。(形式上,对于子数组 C[i], C[i+1], …, C[j],不存在 i <= k1, k2 <= j 其中 k1 % A.length = k2 % A.length)
示例 1:

输入:[1,-2,3,-2]
输出:3
解释:从子数组 [3] 得到最大和 3
示例 2:

输入:[5,-3,5]
输出:10
解释:从子数组 [5,5] 得到最大和 5 + 5 = 10
示例 3:

输入:[3,-1,2,-1]
输出:4
解释:从子数组 [2,-1,3] 得到最大和 2 + (-1) + 3 = 4
示例 4:

输入:[3,-2,2,-3]
输出:3
解释:从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
示例 5:

输入:[-2,-3,-1]
输出:-1
解释:从子数组 [-1] 得到最大和 -1

题解

class Solution {
/*
如果 
全部是正数 那么 最大子数组和 就是 整个数组 遍历一次数组就可以,此时不是环
全部是负数 那么 最大子数组和 就是 最大的负数 遍历一次数组就可以,此时不是环
所以 成环的情况是 既有正数也有负数
此时 有以下情况
前 最大 后 ,此时一次循环就可以找到最大子数组和,不成环
最大 中 后 ,此时一次循环就可以找到最大子数组和,不成环
前 中 最大 ,此时一次循环就可以找到最大子数组和,不成环
最 中 大   ,此时构成环
也就是说 只有当 最大子数组和 在前面 和后面 而不是在中间时 才构成环
也就是说 最后只有两种情况
不构成环时,遍历一次就可以找到最大子数组和
构成环时,去掉中间的和 就是最大子数组和

不构成环时,很简单,之前的子数组和的解法就可以

构成环时,需要分析一下
数组总和-最大和 = 其它位置的和
最 中 大
最大在两边,那么就可以转换为
数组总和-最大和= 中间和
数组总和-中间和= 最大和
所以 中间和是什么呢 ,
若中间和大于0 那么 肯定加上中间和更大 所以 中间和一定小于0 
而且 中间和越小 前后两端的和越大
所以 中间和 就必须是 最小子数组和

所以 要求的结果 就应该是
不成环时,求最大和
成环时,数组总和-最小和
比较两个的值谁更大,更大的就是最大子数组和
*/
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int size = nums.size();
        vector<int>dpMax(size);
        vector<int>dpMin(size);
        dpMax[0]=nums[0];
        dpMin[0]=nums[0];
        int maxCount = nums[0];
        int minCount = nums[0];
        int allCount = nums[0];
        for(int i =1;i<size;i++){
            dpMax[i]=max(dpMax[i-1]+nums[i],nums[i]);
            if(dpMax[i]>maxCount)maxCount=dpMax[i];

            dpMin[i]=min(dpMin[i-1]+nums[i],nums[i]);
            if(dpMin[i]<minCount)minCount=dpMin[i];

            allCount+=nums[i];
        }
        //minCount 一定是个小于0的数
        //allCount-minCount的结果一定比原来的数大
        //如果结果为0 那么 数组里肯定全部是负数
        //换句话说 如果 maxCount 值小于0
        //遍历一遍数组,其中最大的数字是负数
        //那么 这个数组一定全部是负数
        //那么 最小子数组和 就是整个数组的和
        //整个数组的和-整个数组的和 = 0
        //但 必须从数组中选取一个数
        //所以 应该返回maxCount,最大的负数
        //if(allCount-minCount==0)return maxCount;
        if(maxCount<0)return maxCount;
        maxCount = max(maxCount,allCount-minCount);
        return maxCount;
    }
};
喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论