动态规划:连续子数组的最大和

xiaoxiao2021-02-28  8

这个题目写了不下三遍了,次次写还次次想不起来,想起来也还写好几遍才能写对,求一串数组的最大最大子序列和,用动态规划的方法,简直不要太高效。 比如下面这个数组{1,-2,3,10,-4,7,2,-5},最大连续子数组是{3,10,-4,7,2}和为18,不过这个求解过程我们不需要知道最大连续子数组的范围,只要知道值是18就可以。 动态规划的思想就是找到子结构的关系!我们可以这么切入这个关系结构,如果我们有个序列{1,-2,3},显然最大子序列是{3},如果我们在这个序列后面再加入一个数t,我们怎么去求加入一个数之后新的序列的连续子序列{1,-2,3,t}的最大和? 当然得抓住连续这个性质! 设以t为序列尾的最大子序列和为sum,则我们可以很直观地看出sum=max{3+t,t},这样理解起来很简单,因为3就在t前面,而我们已经知道以3为结尾的最大连续子序列和就是3,这个3就是t绕不过去的一个坑。 知道这个关系后我们就可以由题目推出这样一个式子; 设F[n]为下标为n结尾的连续子序列最大和,数组名为num 推出:F[n]=max{F[n-1]+num[n]} 看到这个式子 由这个关系我们就可以很自然地去求解这个问题 代码如下:

int FindMax(char num[],int size) { int *f = new int[size]; f[0] = num[0]; for (int i = 1; i < size; i++) { if (f[i - 1] + num[i] > num[i]) f[i] = f[i - 1] + num[i]; else f[i] = num[i]; } int max = f[0]; for (int i = 1; i < size; i++) if (max < f[i]) max = f[i]; delete[] f; return max; }

可是代码虽然容易看懂,但是我们却开了一块辅助数组啊,这可要不得,仅仅就求个最大和我却开了数组?完全没必要啊,我只要在求f[i]时顺带和max比较下不就行了,而且公式告诉我们了,F[n]只和F[n-1]和num[n]有关系啊,那我存这么多数干嘛???所以我们就简化下代码如下

int FindMax(int num[],int size) { if(size<=0)return 0; int max=num[0]; int tmp=num[0]; for(int i=1;i<size;i++) { tmp=tmp+num[i]; if(num[i]>tmp) tmp=num[i]; if(tmp>max) max=tmp; } return max; }

希望我下次再碰到这种,不会再忘记了。。。。。。毕竟事不过三的。。

转载请注明原文地址: https://www.6miu.com/read-1400341.html

最新回复(0)