`
chriszeng87
  • 浏览: 713882 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

利用动态规划求连续数组最大和以及最大子矩阵的和

阅读更多

题目一:

给定一个整型数组,数组中有正有负,求最大连续子序列的和。

 

解法:

利用动态规划的思想。

设f(n)表示以a[n]为子序列最后一个元素的最大和,则可以有下面的规则:

(1)当f(n-1)<0时,f(n)=a[n];

(2)当n!=0且f(n-1)>0时,f(n)=f(n-1)+a[n]。

用一个nGreatestNum来记录最大值,每次与f(n)进行比较,不断更新即可。

 

题目二:

给定一个二维数组,数组中有正有负,求最大子矩阵的和。

 

解法:

仍然用动态规划的思想。

首先,将二维问题降维处理:

例如,用2 维数组a[1 : m][1 : n]表示给定的m行n列的整数矩阵。子数组a[i1 : i2][j1 : j2]表示左上角和右下角行列坐标分别为(i1, j1)和(i2, j2)的子矩阵。

先按照行排列出所有可能区间,然后,再去求列的范围。

更详细的,当行区间确定之后,剩下就是确定列区间了,一旦确定列区间,最大子矩阵就确定了。

当行区间确定之后,求列区间的方法,可以转化成一维数组的最大连续子序列的问题:对行区间[i1, j1],依次对列进行求和,就得到n个数据的以为数组,根据最大连续子序列的和的求法,就可以获得连续子序列最大和。

仍然用nGreatestNum来记录最大值,算出一个子矩阵的和,就进行比较即可。

 

复杂度分析:

(1)排列出行区间,复杂度为O(M*M);

(2)而求得最大子序列的和复杂度为O(N);

(3)对于行区间确定之后对列求和的复杂度呢?

这里采用“部分和”的做法。

用BC[i][j]表示0到i行、0到j列的总和。

那么对于行区间r->l,求第i列的和:BC[l][i] - B[r-1][i] - B[l][i-1] + B[r-1][i-1]。

而求“部分和”仅需要O(N*M)。可以预先计算好。

因此,算法复杂度为O(N*M*M)。

 

转自:http://blog.csdn.net/yahohi/article/details/7958261

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics