C++动态规划

在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素c[i][j]的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这3个数组元素的值所确定。对于给定的数组元素c[i][j]，可以不借助于数组b而仅借助于c本身在时间内确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的。

如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算c[i][j]时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n))。

n个数(可能是负数）组成的序列a1,a2,…an.求该序列

例如:  序列(-2,11,-4,13,-5,-2) ，最大子段和：

　　　 11 - 4 + 13＝20。

（1）穷举算法： O(n3), O(n2)

将序列a[1:n]从n/2处截成两段：a[1:n/2], a[n/2+1:n]

 

例如:  序列(-2,11,-4,13,-5,-2) ，最大子段和：

　　 11 - 4 + 13＝20。

（1）穷举算法： O(n3), O(n2)

将序列a[1:n]从n/2处截成两段：a[1:n/2], a[n/2+1:n]

一共存在三种情况：

a.最大子段和出现在左边一段

b.最大子段和出现在右边一段

c.最大子段和跨越中间的断点

对于前两种情况，只需继续递归调用，而对于第三种情况：

上一页  1 2 3 4 5 6 7 8  下一页