题目描述
给定一个整数数组，找出总和最大的连续数列，并返回总和。
示例:
输入： [-2,1,-3,4,-1,2,1,-5,4]
输出： 6
解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
解题思路
没有很好的方法，直接暴力遍历所有情况；
class Solution {
public int maxSubArray(int[] nums) {
int max=Integer.MIN_VALUE;
//特殊状态
if(nums==null||nums.length==0)return max;
//前缀和
//prefixSum[1]=nums[0];
//prefixSum[2]=nums[0]+num[1];
//...
//prefixSum[index]=nums[0]+...nums[index-1];
int[] prefixSum=new int[nums.length+1];
prefixSum[0]=0;
for(int index=0;index<nums.length;index++){
prefixSum[index+1]=prefixSum[index]+nums[index];
}
//连续数组长度1~nums.length
for(int len=1;len<=nums.length;len++){
//连续数组起始位置
for(int index=0;index<=nums.length-len;index++){
max=Math.max(max,prefixSum[index+len]-prefixSum[index]);
}
}
return max;
}
}
提交效果：
image-20210321001633448
时间和空间复杂度分析：
时间复杂度：O(n^2)
空间复杂度：O(n)
某大师表示这解法太垃圾了，帮我改了改：
class Solution {
public int maxSubArray(int[] nums) {
int max=Integer.MIN_VALUE;
if(nums==null||nums.length==0)return max;
//最优前缀和数组
int[] prefixSum=new int[nums.length];
//第0个数的前缀和即是第0个数
prefixSum[0]=nums[0];
for(int index=1;index<nums.length;index++){
//若第index-1个数的前缀对第index个数的前缀和有增益效果,则第index个数的前缀和添加增益效果;
if(prefixSum[index-1]>0){
prefixSum[index]=prefixSum[index-1]+nums[index];
}else{
//若第index-1个数的前缀对第index个数的前缀和没增益效果,则直接舍去第index-1个数前缀和的累赘
prefixSum[index]=nums[index];
}
}
//思考，现在的优先前缀和是啥？
//第index个数的前缀和是必然包含第index个数的一个和数;兄弟，别怀疑,这就是一句废话！！
//此时反向思考，本题目需要求整数组nums中连续数列的最大和数，这里转达一个意思即我们得在一组数中找到一个最大值，但是这组数是啥？这组数是以第0个数为结尾的连续数列最大值，以第1个数为结尾的连续数列最大值，以第2个数为结尾的连续数列最大值... 以第index个数为结尾的连续数列最大值...以第(nums.length-1)个数为结尾的连续数列最大值;你细品，慢慢品，不就是上面的最优前缀和吗？
for(int index=0;index<nums.length;index++){
max=Math.max(max,prefixSum[index]);
}
return max;
}
}
提交效果：
image-20210321001502408
大师不愧为大师，稍微修改修改，就提升了这么多，真滴牛啊！！
时间空间复杂度分析：
时间复杂度: O(n)
空间复杂度: O(n)
复盘：
某大师的基本思路是什么？ DP
熟悉DP的人都知道DP通常具有三个特性，重叠子问题，状态转移方程，最优子结构;
首先本题需要理顺的问题便是这里的最优子结构在如何构造问题？
数组nums的连续数组最大和数 = {以第0个数为尾数的前缀子数组最大和数，以第1个数为尾数的前缀子数组最大和数...以第n-1个数为尾数的前缀子数组最大和数} 此集合最大值；
此时问题转变为求第index个数为尾数前缀子数组？
设dp(i)表示:以第i个数为尾数的前缀子数组最大和数，若dp(i-1)<0,则此时的上个前缀和有点像个累赘，只会导致当前的dp(i)更小，若dp(i)>0,则可添加上个前缀和；
状态转移方程：dp(i)=Math.max(dp(i-1)+nums[i], nums[i])
重新整理：
class Solution {
public int maxSubArray(int[] nums) {
int max=Integer.MIN_VALUE;
if(nums==null||nums.length==0)return max;
//子结构最大值
int[] subMax=new int[nums.length];
subMax[0]=nums[0];
max=subMax[0];
//子结构生成时即比较最大值
for(int index=1;index<nums.length;index++){
subMax[index]=Math.max(subMax[index-1]+nums[index],nums[index]);
max=Math.max(max,subMax[index]);
}
return max;
}
}
