LeetCode第53题：最大子数组和（C++动态规划与Java分治法解析，推荐二次练习）

给你一个整数数组 nums &＃xff0c;请你找出一个具有最大和的连续子数组&＃xff08;子数组最少包含一个元素&＃xff09;&＃xff0c;返回其最大和。子数组 是数组中的一个连续部分。示例 1&＃xff1a;输入&＃xff1a;nums &＃61; [-2,1,-3,4,-1,2,1,-5,4]
输出&＃xff1a;6
解释&＃xff1a;连续子数组 [4,-1,2,1] 的和最大&＃xff0c;为 6 。
示例 2&＃xff1a;输入&＃xff1a;nums &＃61; [1]
输出&＃xff1a;1
示例 3&＃xff1a;输入&＃xff1a;nums &＃61; [5,4,-1,7,8]
输出&＃xff1a;23提示&＃xff1a;1 <&＃61; nums.length <&＃61; 105
-104 <&＃61; nums[i] <&＃61; 104进阶&＃xff1a;如果你已经实现复杂度为 O(n) 的解法&＃xff0c;尝试使用更为精妙的 分治法 求解。来源&＃xff1a;力扣&＃xff08;LeetCode&＃xff09;
链接&＃xff1a;https://leetcode-cn.com/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权&＃xff0c;非商业转载请注明出处。

实现思路1&＃xff1a;

动态规划&＃xff0c;一个一个考虑&＃xff0c;列出这样的状态转移方程。

 实现代码1&＃xff1a;

class Solution {
public:int maxSubArray(vector& nums) {int len&＃61;nums.size(),maxn&＃61;-100000;int dp[len];dp[0]&＃61;nums[0];for(int i&＃61;1;idp[0]?maxn:dp[0];}
};

实现思路2&＃xff1a;

分治

实现代码&＃xff1a;

class Solution {public class Status{public int lsum;public int rsum;public int xsum;public int isum;//lsum表示从左端开始的最大子序列和,rsum表示从右端开始的最大子序列和,//xsum表示整个区间的最大子序列和,isum表示整个区间的和。public Status(int lsum,int rsum,int xsum,int isum){this.lsum&＃61;lsum;this.rsum&＃61;rsum;this.xsum&＃61;xsum;this.isum&＃61;isum;}}public int maxSubArray(int[] nums) {Status status&＃61;get(nums,0,nums.length-1);return status.xsum;}public Status get(int[] a,int l,int r){if (l &＃61;&＃61; r) {return new Status(a[l], a[l], a[l], a[l]);}int m&＃61;(l&＃43;r)/2;Status ls&＃61;get(a,l,m);Status rs&＃61;get(a,m&＃43;1,r);int lsu&＃61;Math.max(ls.lsum,ls.isum&＃43;rs.lsum);int rsu&＃61;Math.max(rs.rsum,rs.isum&＃43;ls.rsum);int xsu&＃61;Math.max(Math.max(ls.xsum,rs.xsum),ls.rsum&＃43;rs.lsum);int isu&＃61;ls.isum&＃43;rs.isum;return new Status(lsu,rsu,xsu,isu);}
}