#yyds干货盘点# LeetCode 热题 HOT 100：最大子数组和

2 years ago

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：最大子数组和

精选原创

灰太狼_cxh 2022-09-29 17:24:05 博主文章分类：leetcode ©著作权

文章标签 子数组数组代码实现 文章分类 Java 编程语言 阅读数186

给你一个整数数组 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);
}
}