原题链接:Maximum Subarray
题目:
Given an integer array nums
, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
分析:
很显然,这是一道动态规划的题目,面对DP问题,那我们首先第一反应暴力求解(只是过程),暴力求解我们只需要将每个子段求和,然后更新max的值,就能很轻易求出题解,暴力求解代码如下:
int maxSubArray(int* nums, int numsSize){ int i=0,j=0; int max=nums[0]; for(i=0;i<numsSize;i++) for(j=0;j<=i;j++){ int k,sum=0; for(k=j;k<=i;k++){ sum+=nums[k]; } if(max<sum) max=sum; } return max; }
但是我们会发现,这样的话,算法复杂度在n2,那好,下一步,我们优化这个算法。我们用一个数代替一类数,那么,我们的算法复杂度就能降到n。具体怎么将呢;别急,看下面。
我们用f[i]代替所有以i结尾的子段,那么我们就用f[i]代替了这一类数(以i结尾的子段),那就是f[i],那么我们只需求出所有以i结尾的子段的和,遍历数组,求出最大值便是答案。那么我们继续发现还能优化,在所有以i结尾的子段里,有一个共同的值,那就是f[i],那么我们只需求出所有以i结尾的子段的但是不包括f[i]这个值的子段的最大值,最后加上f[i],对我们的最大值无影响;说了这么多,一张图了事:
那么我们大体思想是max(f[0],f[1]........f[n-2],f[n-1])
那么代码如下:
#define Max(a,b) ((a)>(b)?(a):(b))//宏定义返回a,b最大值 int maxSubArray(int* nums, int numsSize){ int maxn=nums[0],last=0,i=0; for(i=0;i<numsSize;i++){ int now=Max(last,0)+nums[i];//计算除去f[i]以外所有以f[i]结尾的子段 maxn=Max(maxn,now); last=now;//更新last } return maxn; }
以上就是题解,总的来说,这个DP算是偏简单的,思路也不是那么难,要是还有不懂,欢迎评论;
支付宝扫一扫
微信扫一扫