代码拉取完成，页面将自动刷新
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
使用dp的方法就是O(n)的方法。如果dp[i]表示以第i个结尾的最大序列和，而这个dp的状态方程为：
dp[0]=a[0]
dp[i]=max(dp[i-1]+a[i],a[i])
也不难解释，如果以前一个为截至的最大子序列和大于0，那么就连接本个元素，否则本个元素就自立门户。
实现代码为：
public int maxSubArray(int[] nums) {
int dp[]=new int[nums.length];
int max=nums[0];
dp[0]=nums[0];
for(int i=1;i<nums.length;i++)
{
dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
if(dp[i]>max)
max=dp[i];
}
return max;
}
至于分治算法，这题复杂度dp为O(n),分治为O(nlogn).并不算快，而分治主要运用递归的过程先分再和，如果当然函数为maxsub(int nums[],int left,int right)最大的可能在以下三种情况产生：
其中中间部分就是分别向左向右进行拓展取最大了。ac代码为(2ms)：
public int maxSubArray(int[] nums) {
int max=maxsub(nums,0,nums.length-1);
return max;
}
int maxsub(int nums[],int left,int right)
{
if(left==right)
return nums[left];
int mid=(left+right)/2;
int leftmax=maxsub(nums,left,mid);
int rightmax=maxsub(nums,mid+1,right);
int midleft=nums[mid];
int midright=nums[mid+1];
int team=0;
for(int i=mid;i>=left;i--)
{
team+=nums[i];
if(team>midleft)
midleft=team;
}
team=0;
for(int i=mid+1;i<=right;i++)
{
team+=nums[i];
if(team>midright)
midright=team;
}
int max=midleft+midright;//中间的最大值
if(max<leftmax)
max=leftmax;
if(max<rightmax)
max=rightmax;
return max;
}
原创不易，bigsai请你帮两件事帮忙一下:
star支持一下， 您的肯定是我在平台创作的源源动力。
微信搜索「bigsai」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。
记得关注、咱们下次再见！
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。