昆明网站建设平台,网站推广是做什么的,公司官网网站搭建,域名备案平台一、题目
给你一个整数数组nums#xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。子数组 是数组中的一个连续部分。
示例 1#xff1a; 输入#xff1a;nums [-2,1,-3,4,-1,2,1,-5,4] 输出#…
一、题目
给你一个整数数组nums请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。子数组 是数组中的一个连续部分。
示例 1 输入nums [-2,1,-3,4,-1,2,1,-5,4] 输出6 解释连续子数组[4,-1,2,1]的和最大为6。
示例 2 输入nums [1] 输出1
示例 3 输入nums [5,4,-1,7,8] 输出23 1 nums.length 105 -104 nums[i] 104 进阶 如果你已经实现复杂度为O(n)的解法尝试使用更为精妙的 分治法 求解。
二、代码
【1】动态规划 假设nums数组的长度是n下标从0到n−1。我们用f(i)代表以第i个数结尾的「连续子数组的最大和」那么很显然我们要求的答案就是max0≤i≤n−1{f(i)}因此我们只需要求出每个位置的f(i)然后返回f数组中的最大值即可。那么我们如何求f(i)呢我们可以考虑nums[i]单独成为一段还是加入f(i−1)对应的那一段这取决于nums[i]和f(i−1)nums[i]的大小我们希望获得一个比较大的于是可以写出这样的动态规划转移方程f(i)max{f(i−1)nums[i],nums[i]}不难给出一个时间复杂度O(n)、空间复杂度O(n)的实现即用一个f数组来保存f(i)的值用一个循环求出所有f(i)。考虑到f(i)只和f(i−1)相关于是我们可以只用一个变量pre来维护对于当前f(i)的f(i−1)的值是多少从而让空间复杂度降低到O(1)这有点类似「滚动数组」的思想。
class Solution {public int maxSubArray(int[] nums) {int pre 0, maxAns nums[0];for (int x : nums) {pre Math.max(pre x, x);maxAns Math.max(maxAns, pre);}return maxAns;}
}时间复杂度 O(n)其中n为nums数组的长度。我们只需要遍历一遍数组即可求得答案。 空间复杂度 O(1)。我们只需要常数空间存放若干变量。
【2】分治 这个分治方法类似于「线段树求解最长公共上升子序列问题」的pushUp操作。 也许读者还没有接触过线段树没有关系方法二的内容假设你没有任何线段树的基础。当然如果读者有兴趣的话推荐阅读线段树区间合并法解决多次询问的「区间最长连续上升序列问题」和「区间最大子段和问题」还是非常有趣的。
我们定义一个操作get(a, l, r)表示查询a序列[l,r]区间内的最大子段和那么最终我们要求的答案就是get(nums, 0, nums.size() - 1)。如何分治实现这个操作呢对于一个区间[l,r]我们取m⌊lr2⌋对区间[l,m]和[m1,r]分治求解。当递归逐层深入直到区间长度缩小为1的时候递归「开始回升」。这个时候我们考虑如何通过[l,m]区间的信息和[m1,r]区间的信息合并成区间[l,r]的信息。最关键的两个问题是 1、我们要维护区间的哪些信息呢 2、我们如何合并这些信息呢
对于一个区间[l,r]我们可以维护四个量 1、lSum表示[l,r]内以l为左端点的最大子段和 2、rSum表示[l,r]内以r为右端点的最大子段和 3、mSum表示[l,r]内的最大子段和 4、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要么等于「左子区间」的iSum加上「右子区间」的lSum二者取大。 3、对于[l,r]的rSum同理它要么等于「右子区间」的rSum要么等于「右子区间」的iSum加上「左子区间」的rSum二者取大。 4、当计算好上面的三个量之后就很好计算[l,r]的mSum了。我们可以考虑[l,r]的mSum对应的区间是否跨越m——它可能不跨越m也就是说[l,r]的mSum可能是「左子区间」的mSum和 「右子区间」的mSum中的一个它也可能跨越m可能是「左子区间」的rSum和 「右子区间」的lSum求和。三者取大。
这样问题就得到了解决。
class Solution {public class Status {public int lSum, rSum, mSum, iSum;public Status(int lSum, int rSum, int mSum, int iSum) {this.lSum lSum;this.rSum rSum;this.mSum mSum;this.iSum iSum;}}public int maxSubArray(int[] nums) {return getInfo(nums, 0, nums.length - 1).mSum;}public Status getInfo(int[] a, int l, int r) {if (l r) {return new Status(a[l], a[l], a[l], a[l]);}int m (l r) 1;Status lSub getInfo(a, l, m);Status rSub getInfo(a, m 1, r);return pushUp(lSub, rSub);}public Status pushUp(Status l, Status r) {int iSum l.iSum r.iSum;int lSum Math.max(l.lSum, l.iSum r.lSum);int rSum Math.max(r.rSum, r.iSum l.rSum);int mSum Math.max(Math.max(l.mSum, r.mSum), l.rSum r.lSum);return new Status(lSum, rSum, mSum, iSum);}
}假设序列a的长度为n。 时间复杂度 假设我们把递归的过程看作是一颗二叉树的先序遍历那么这颗二叉树的深度的渐进上界为O(logn)这里的总时间相当于遍历这颗二叉树的所有节点故总时间的渐进上界是O(∑i1logn2i−1)O(n)故渐进时间复杂度为O(n)。 空间复杂度 递归会使用O(logn)的栈空间故渐进空间复杂度为O(logn)。
题外话 「方法二」相较于「方法一」来说时间复杂度相同但是因为使用了递归并且维护了四个信息的结构体运行的时间略长空间复杂度也不如方法一优秀而且难以理解。那么这种方法存在的意义是什么呢
对于这道题而言确实是如此的。但是仔细观察「方法二」它不仅可以解决区间[0,n−1]还可以用于解决任意的子区间[l,r]的问题。如果我们把[0,n−1]分治下去出现的所有子区间的信息都用堆式存储的方式记忆化下来即建成一棵真正的树之后我们就可以在O(logn)的时间内求到任意区间内的答案我们甚至可以修改序列中的值做一些简单的维护之后仍然可以在O(logn)的时间内求到任意区间内的答案对于大规模查询的情况下这种方法的优势便体现了出来。这棵树就是上文提及的一种神奇的数据结构——线段树。
