力扣数据结构入门专栏分析 ②
一、题目描述：
题目链接: 53. 最大子数组和
给你一个整数数组 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) 的解法，尝试使用更为精妙的 分治法 求解。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/maximum-subarray著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、思路分析：
这道题考察了什么思想？你的思路是什么？
- 这道题本仙女刚开始看了没什么感觉，不知道从何下手。望着这道题目20分钟没动一下手。
我不由得怀疑这也是简单题目吗？后来想到了一种暴力解法：
如果是第k个元素结尾的话，我们就把前面从第一个元素开始到第k个的连续和全部求一遍，然后保存最大值，后面第k+1个把前面从第一个元素开始到第k+1个的连续和全部求一遍，然后与前面保存的最大值进行比较。这样不就得到最大值了吗？
做题的时候是不是一次通过的，遇到了什么问题，需要注意什么细节？
- 结果上面说的这种暴力方法果然超时了...
因为不需要求出是哪个子序列和最大，只需要和即可，于是几经辗转用上了动态规划。
后来看到大佬写的还可以进行空间优化，只是我理解起来有点困难。下方用C写的就是我根据大佬的思路写的。
其他人的题解是什么?
- 我还看到了大佬用分治方法的思路，膜拜一波~
网络异常，图片无法展示|
classSolution {
publicclassStatus {
publicintlSum, rSum, mSum, iSum;
publicStatus(intlSum, intrSum, intmSum, intiSum) {
this.lSum=lSum;
this.rSum=rSum;
this.mSum=mSum;
this.iSum=iSum;
}
}
publicintmaxSubArray(int[] nums) {
returngetInfo(nums, 0, nums.length-1).mSum;
}
publicStatusgetInfo(int[] a, intl, intr) {
if (l==r) {
returnnewStatus(a[l], a[l], a[l], a[l]);
}
intm= (l+r) >>1;
StatuslSub=getInfo(a, l, m);
StatusrSub=getInfo(a, m+1, r);
returnpushUp(lSub, rSub);
}
publicStatuspushUp(Statusl, Statusr) {
intiSum=l.iSum+r.iSum;
intlSum=Math.max(l.lSum, l.iSum+r.lSum);
intrSum=Math.max(r.rSum, r.iSum+l.rSum);
intmSum=Math.max(Math.max(l.mSum, r.mSum), l.rSum+r.lSum);
returnnewStatus(lSum, rSum, mSum, iSum);
}
}
三、AC 代码：
动态规范
Java:
classSolution {
publicintmaxSubArray(int[] nums) {
int[] dp=newint[nums.length];
dp[0] =nums[0];
intres=dp[0];
for(inti=1;i<nums.length;i++){
if(dp[i-1]<0){
dp[i] =nums[i];
}else{
dp[i] =dp[i-1] +nums[i];
}
res=Math.max(res, dp[i]);
}
returnres;
}
}
C：
int max(int a,int b){
if(a>b) return a;
return b;
}
int maxSubArray(int* nums, int numsSize) {
int pre = 0, maxAns = nums[0];
for (int i = 0; i < numsSize; i++) {
pre = max(pre + nums[i], nums[i]);
maxAns = max(maxAns, pre);
}
return maxAns;
}
四、总结：
这道题目对理解动态规范很有帮助！有时间要多做几遍，另外如果可以的话，我们应该尝试输出最大子序列。
