**题目：**给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例： 进阶： 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
方法一：动态规划： 思路 这道题用动态规划的思路并不难解决，比较难的是后文提出的用分治法求解，但由于其不是最优解法，所以先不列出来 动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans 如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字 如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字 每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果 时间复杂度：O(n)
class Solution { public int maxSubArray(int[] nums) { int ans = nums[0]; int sum = 0; for(int num: nums) { if(sum > 0) { sum += num; } else { sum = num; } ans = Math.max(ans, sum); } return ans; } }方法二：分治 思路和算法
这个分治方法类似于「线段树求解 LCIS 问题」的 pushUp 操作。 也许读者还没有接触过线段树，没有关系，方法二的内容假设你没有任何线段树的基础。当然，如果读者有兴趣的话，推荐看一看线段树区间合并法解决 多次询问 的「区间最长连续上升序列问题」和「区间最大子段和问题」，还是非常有趣的。
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); } }