6
#yyds干货盘点# LeetCode 热题 HOT 100：最大子数组和
source link: https://blog.51cto.com/u_13321676/5723603
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# LeetCode 热题 HOT 100：最大子数组和
精选 原创给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
输入：nums = [1]
输入：nums = [5,4,-1,7,8]
输出：23
代码实现：
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);
}
}
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);
}
}
- 赞
- 收藏
- 评论
- 分享
- 举报
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK