題目一：

給定一個整型數組，數組中有正有負，求最大連續子序列的和。

?

解法：

利用動態規劃的思想。

設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)。

版權聲明：本文為博主原創文章，未經博主允許不得轉載。

轉載于:https://www.cnblogs.com/wangicter/archive/2012/09/08/4767293.html

總結

以上是生活随笔為你收集整理的利用动态规划求连续数组最大和以及最大子矩阵的和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。