最大子数组和

经典题目:给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组 是数组中的一个连续部分。

注意:题目要求子数组最少包含一个元素,所以返回结果可能为负(若所有元素负,则将返回最大的一个负数)。倘若允许子数组为空(结果为0),则要怎么修改?

示例 1:

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。

https://leetcode-cn.com/problems/maximum-subarray/

解1 动态规划:

1
2
3
4
5
6
7
8
9
10
int maxSubArray(vector<int>& nums) {
if(nums.empty()) return 0;
size_t n=nums.size();
vector<int> ans(n); // 代表以nums[i]为结尾的连续最大和
ans[0]=nums[0];
for(int i=1;i<n;i++) {
ans[i]=max(ans[i-1]+nums[i],nums[i]);
}
return *max_element(ans.begin(), ans.end());
}

刻画解的状态结构:f(i)代表以nums[i]为结尾的连续最大和
状态转移方程:f(i)=max{ f(i-1)+nums[i], nums[i] }
解释:选择是将nums[i]以nums[i-1]为结尾的最优解,或是选择以nums[i]单独成为解

注:我在第一次尝试解答时,将状态结构f(i)构造为了 代表以nums[1]…num[i]可以包含的最优解,
然而后续遭遇了困难,因为我无法简单确定nums[1]…num[i-1]的最优解位置,可能不在末尾而在中间,难以继续转移。
以后要注意不同的结构构造方法,并且注意怎样构造才更方便更简洁。

解2 分治法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int maxCrossingSubArray(vector<int>& nums, int left, int mid, int right) {
int leftSum=0;
for(int i=mid-1, sum=0; i>=left; i--) {
sum+=nums[i];
if(sum > leftSum) {
leftSum = sum;
}
}
int rightSum=0;
for(int i=mid+1, sum=0; i<=right; i++) {
sum+=nums[i];
if(sum > rightSum) {
rightSum = sum;
}
}
return leftSum+nums[mid]+rightSum;
}
int maxSubArray(vector<int>& nums, int left, int right) {
if (left==right) {
return nums[left]; // base case
}
int mid = (left+right)/2;
int rLeft = maxSubArray(nums, left, mid);
int rRight = maxSubArray(nums, mid+1, right);
int rMid = maxCrossingSubArray(nums, left, mid, right);
return max(max(rLeft, rRight), rMid);
}
int maxSubArray(vector<int>& nums) {
return maxSubArray(nums, 0, nums.size()-1);
}

注:
maxCrossingSubArray的实现
注意左右的最大和要分开计算。想想若使用同一个sum变量会发生什么?
要注意解中肯定可能包含负数,并非遇到负数就要中断。如3 -1 5肯定比3大。

解3 分治:
作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
著作权归作者所有。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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(vector<int> &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(vector<int>& nums) {
return get(nums, 0, nums.size() - 1).mSum;
}

该解采用了不同的分治设计,具体可以参见LeetCode答案。

Donate
  • Copyright: Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2014-2022 听寒
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信