济南网站制,wordpress 闭站,如何做国外的网站,中国建设工程信息网站题目#xff1a;
给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。
子数组是数组中的一个连续部分。 解法一#xff08;枚举法-时间复杂度超限#xff09;#xff1a;
…题目
给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
子数组是数组中的一个连续部分。 解法一枚举法-时间复杂度超限
暴力法nums的数组元素被重复访问多次导致时间复杂度超限仅作为与下面两种方法的对比参考并不是本题的正确解时间复杂度为O(n^2)超限如下为实现代码
class Solution{
public:int maxSubArray(vectorint nums){//类似寻找最大最小值的题目初始值一定要定义成理论上的最小最大值int max INT_MIN;int numsSize int(nums.size());for (int i 0; i numsSize; i){ int sum 0;for (int j i; j numsSize; j){ sum nums[j];if (sum max){max sum;}}}return max;}
};
解法二动态规划
假设nums数组的长度是n下标从0到n-1。我们用f(i)代表以第i个数结尾的【连续子数组的最大和】很显然我们要求的答案就是max(0≤i≤n-1){f(i)}。
因此我们只需要求出每个位置的f(i)然后返回f数组中的最大值即可。那么我们如何求f(i)呢我们可以考虑nums[i]单独成为一段还是加入f(i-1)对应的那一段这取决于nums[i]和f(i-1)nums[i]的大小我们希望获得一个比较大的于是可以写出动态规划转移方程 于是我们可以只用一个变量pre来维护对于当前f(i)的f(i-1)的值是多少。
如果编号为 i 的子问题的结果是负数或者 0 那么编号为 i 1 的子问题就可以把编号为 i 的子问题的结果舍弃掉而子问题的定义必须以一个数结尾因此如果子问题 i 的结果是负数或者 0那么子问题 i 1 的答案就是以 nums[i] 结尾的那个数。题目只要求返回结果不要求得到最大的连续子数组是哪一个。这样的问题通常可以使用「动态规划或者贪心算法」解决。如下为实现代码
class Solution {
public:int maxSubArray(vectorint nums) {//pre表示当前f(i)下的f(i-1)的值初始时pre为0//maxAns为截止至第i个索引元素时最大的子数组和最终的返回值int pre 0, maxAns nums[0];for (const auto x: nums) {pre max(pre x, x);maxAns max(maxAns, pre);}return maxAns;}
};
解法三分治思想
我们定义一个操作get(a, l, r)表示查询a序列[l,r]区间内的最大子段和那么最终要求的答案就是get(nums, 0, nums.size()-1)。如何分治实现这个操作呢对于一个区间[l,r]我们取对区间[l,m]和[m1,r]分治求解。当递归逐层深入直到长度缩小为1的时候递归【开始回升】。这个时候我们考虑如何通过[l,m]区间的信息和[m1,r]区间的信息合并成区间[l,r]的信息。最关键的两个问题是
我们要维护区间的哪些信息呢我们如何合并这些信息呢
对于一个区间 [l,r]我们可以维护四个量
lSum 表示 [l,r] 内以 l 为左端点的最大子段和rSum 表示 [l,r] 内以 r 为右端点的最大子段和mSum 表示 [l,r] 内的最大子段和iSum 表示 [l,r] 的区间和
以下简称[l,m]为[l,r]的左子区间[m1,r]为[l,r]的右子区间 。我们考虑如何维护这些信息呢如何通过左右子区间的信息合并得到[l,r]的信息。对于长度为1的区间[i,i]四个量的值都和nums[i]相等。对于长度大于 1 的区间
1、首先最好维护的是 iSum区间 [l,r] 的 iSum 就等于【左子区间】的 iSum 加上【右子区间】的 iSum。
2、对于[l,r]的lSum存在两种可能它要么等于【左子区间】的lSum要么等于【左子区间】的lSum加上【右子区间的】lSum二者取最大。
3、对于[l,r]的rSum同理它要么等于【右子区间】的rSum要么等于【右子区间】的rSum加上【左子区间】的rSum加上右子区间的rSum。
4、当计算好上面的三个量之后就很好计算[l,r]的mSum了。我们可以考虑[l,r]的mSum对应的区间是否跨越m——它可能不跨越m也就是说[l,r]的mSum可能是【左子区间】的mSum和【右子区间】的mSum中的一个它也可能跨越m可能是【左子区间】的rSum和【右子区间】的lSum求和。三者取最大。这样问题就得到了解决。如下为实现代码
class Solution {
public:struct Status {int lSum, rSum, mSum, iSum;};Status pushUp(Status l, Status r) {int iSum l.iSum r.iSum;int lSum max(l.lSum, l.iSum r.lSum);int rSum max(r.rSum, r.iSum l.rSum);int mSum max(max(l.mSum, r.mSum), l.rSum r.lSum);return (Status) {lSum, rSum, mSum, iSum};};Status get(vectorint a, int l, int r) {if (l r) {return (Status) {a[l], a[l], a[l], a[l]};}int m (l r) 1;Status lSub get(a, l, m);Status rSub get(a, m 1, r);return pushUp(lSub, rSub);}int maxSubArray(vectorint nums) {return get(nums, 0, nums.size() - 1).mSum;}
};
时间复杂度假设我们把递归的过程看作是一颗二叉树的先序遍历那么这颗二叉树的深度的渐进上界为 O(logn)这里的总时间相当于遍历这颗二叉树的所有节点故总时间的渐进上界是 故渐进时间复杂度为 O(n)。空间复杂度递归会使用 O(logn) 的栈空间故渐进空间复杂度为 O(logn)。
分治方法相比动态规划方法二的优势它不仅可以解决区间 [0,n−1]还可以用于解决任意的子区间 [l,r] 的问题。如果我们把 [0,n−1] 分治下去出现的所有子区间的信息都用堆式存储的方式记忆化下来即建成一棵真正的树之后我们就可以在 O(logn) 的时间内求到任意区间内的答案我们甚至可以修改序列中的值做一些简单的维护之后仍然可以在 O(logn) 的时间内求到任意区间内的答案对于大规模查询的情况下这种方法的优势便体现了出来。这棵树就是上文提及的一种神奇的数据结构——线段树。
笔者小记
1、动态规划与分治法和贪心法类似都是将问题分解为更小的子问题并通过求解子问题来得到全局最优解。然而它们在处理子问题的方式上有所不同
贪心法当前选择依赖于已经作出的所有选择但不依赖于有待于做出的选择和子问题。它自顶向下一步一步地作出贪心选择。分治法各个子问题是独立的一旦递归地求出各子问题的解后自下而上地将子问题的解合并成问题的解。动态规划允许子问题不独立通过自身子问题的解作出选择对每一个子问题只解一次并将结果保存起来避免每次碰到时都要重复计算。
解决问题的时候应根据题目要求划分采用贪心思想、动态规划思想、分治思想三类思想的哪类问题再进行代码的实现三种思想时间复杂度都较低单层循环逻辑可实现。
