给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

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

进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

思路与代码

动态规划

dp[i] 表示以第i个结尾的最大序列和（至少包含nums[i]，因为子序列比必定至少包含一个数） 动态转移：

如果dp[i-1] <= 0 则dp[i] = nums[i]如果dp[i-1] > 0 则dp[i] = nums[i] + dp[i-1]

时间复杂度 O(n) 空间复杂度O(n)

class Solution { //有dp数组的形式 public int maxSubArray(int[] nums) { int[] dp = new int[nums.length]; dp[0] = nums[0]; int max = nums[0]; for (int i = 1; i < nums.length; i++){ if (dp[i-1] > 0) dp[i] = dp[i-1] + nums[i]; else dp[i] = nums[i]; max = Math.max(max, dp[i]); } return max; } }

时间复杂度 O(n) 空间复杂度O(1)

class Solution { //无dp数组的形式 sum表示以第i个结尾的最大序列和（相当于上面的dp[i]） public int maxSubArray(int[] nums) { int max = nums[0]; int sum = 0; for (int i = 0; i < nums.length; i++){ if (sum > 0) sum += nums[i]; else sum = nums[i]; max = Math.max(max, sum); } return max; } }

分治算法

这个分治方法类似于 线段树求解 LCIS 问题 的 pushUp 操作。（自行搜索）

对于一个区间 [l,r]，我们可以维护四个量：

lSum 表示 [l,r]内以 ll 为左端点的最大子段和rSum 表示 [l,r] 内以 rr 为右端点的最大子段和mSum 表示 [l,r] 内的最大子段和iSum 表示 [l,r] 的区间和

[l,m]为 [l,r] 的「左子区间」，[m+1,r] 为 [l,r] 的「右子区间」

代码中getInfo(int[] nums, int l, int r)方法是得到 [l,r] 区间的四个状态量，可以转化为由左子区间[l,r] 和右子区间`[m+1,r]的四个状态量合并得到。

当l == r时，四个状态量相等。

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); } }