元素和最大的子矩陣
題目描述
輸入一個n級方陣,請找到此矩陣的一個子矩陣,此子矩陣的各個元素的和是所有子矩陣中最大的,輸出這個子矩陣及這個最大的和。
關于輸入
首先輸入方陣的級數n,
然后輸入方陣中各個元素。
關于輸出
輸出子矩陣,
最后一行輸出這個子矩陣的元素的和。
例子輸入
4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2
例子輸出
9 2 -4 1 -1 8 15
解題分析
這個程序是一個求解最大子矩陣和的問題。可以使用動態規劃和Kadane算法。這個問題可以描述為:給定一個二維數組,找出其中的一個子矩陣,使得這個子矩陣中所有元素的和最大。
這個程序的主要思路如下:
1. 讀取一個整數`n`,然后讀取一個`n`x`n`的整數矩陣`a`。
2. 計算`total`數組,`total[i][j]`表示從`a[0][j]`到`a[i][j]`的元素之和。如果`i`為0,`total[i][j]`就等于`a[i][j]`,否則`total[i][j]`就等于`total[i-1][j]+a[i][j]`。
3. 遍歷所有可能的子矩陣。對于每一個子矩陣,計算其元素之和,然后與當前最大的子矩陣和進行比較。如果新的子矩陣和更大,就更新最大的子矩陣和,以及對應的子矩陣的左上角和右下角的坐標。
4. 在計算子矩陣和的過程中,使用了Kadane算法。Kadane算法可以在O(n)的時間復雜度內求解最大子數組和的問題。在這個程序中,Kadane算法被用來求解每一行元素之和的最大值。
5. 最后,打印出最大子矩陣和,以及對應的子矩陣的元素。
Kadane算法是一個用于解決最大子數組和問題的動態規劃算法。最大子數組和問題可以描述為:在一個一維數組中,找出一個連續的子數組,使得這個子數組中所有元素的和最大。
Kadane算法的基本思想是,對于數組中的每個位置,計算以該位置為結束點的所有子數組中,和最大的那個子數組的和。然后,從這些和中找出最大的那個,就是最大子數組和。
具體來說,算法的步驟如下:
1. 初始化兩個變量,`max_so_far`和`max_ending_here`,都設為數組的第一個元素。`max_so_far`表示到目前為止找到的最大子數組和,`max_ending_here`表示以當前位置為結束點的子數組的最大和。
2. 對于數組中的每個位置,首先計算`max_ending_here + array[i]`,然后與`array[i]`比較,取較大的那個作為新的`max_ending_here`。這一步表示,如果加上當前元素能使子數組和更大,就加上當前元素,否則就從當前元素開始新的子數組。
3. 然后,比較`max_so_far`和`max_ending_here`,取較大的那個作為新的`max_so_far`。這一步表示,如果`max_ending_here`比`max_so_far`大,就更新`max_so_far`。
4. 重復上述步驟,直到遍歷完數組。
5. 最后,`max_so_far`就是最大子數組和。
Kadane算法的時間復雜度是O(n),因為它只需要遍歷一次數組。這使得它在處理大規模數據時非常高效。
舉個例子:
讓我們通過一些具體的例子來理解Kadane算法。
假設我們有一個數組`{-2, -3, 4, -1, -2, 1, 5, -3}`,我們想找到這個數組中,和最大的子數組。
我們可以按照Kadane算法的步驟來操作:
1. 初始化`max_so_far`和`max_ending_here`為數組的第一個元素`-2`。
2. 對于數組中的第二個元素`-3`,我們先計算`max_ending_here + array[i]`,得到`-2 - 3 = -5`,然后與`-3`比較,取較大的那個作為新的`max_ending_here`,所以`max_ending_here`更新為`-3`。然后,比較`max_so_far`和`max_ending_here`,取較大的那個作為新的`max_so_far`,所以`max_so_far`保持不變,還是`-2`。
3. 對于數組中的第三個元素`4`,我們先計算`max_ending_here + array[i]`,得到`-3 + 4 = 1`,然后與`4`比較,取較大的那個作為新的`max_ending_here`,所以`max_ending_here`更新為`4`。然后,比較`max_so_far`和`max_ending_here`,取較大的那個作為新的`max_so_far`,所以`max_so_far`更新為`4`。
4. 以此類推,我們可以得到以下的結果:
?? ```
?? i = 3, array[i] = -1, max_ending_here = 3, max_so_far = 4
?? i = 4, array[i] = -2, max_ending_here = 1, max_so_far = 4
?? i = 5, array[i] = 1, max_ending_here = 2, max_so_far = 4
?? i = 6, array[i] = 5, max_ending_here = 7, max_so_far = 7
?? i = 7, array[i] = -3, max_ending_here = 4, max_so_far = 7
?? ```
5. 最后,我們得到的`max_so_far`就是最大子數組和,也就是`7`。這個最大和的子數組是`{4, -1, -2, 1, 5}`。
通過這個例子,我們可以看到,Kadane算法可以有效地找到最大子數組和,而且只需要遍歷一次數組。
代碼實現
#include <iostream>
using namespace std;int a[1000][1000];
int total[1000][1000];
int result[1000];
int n;int getmax(int &start,int &end){int local_start=0;int maxSum=result[0];int cur_max=result[0];for(int i=1;i<n;i++){if(result[i]>cur_max+result[i]){cur_max=result[i];local_start=i;}else{cur_max+=result[i];}if(cur_max>maxSum){start=local_start;end=i;maxSum=cur_max;}}return maxSum;
}int main() {cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++){cin>>a[i][j];}for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(i==0) total[i][j]=a[i][j];else total[i][j]=total[i-1][j]+a[i][j];}int top=0,bottom=0,left=0,right=0;int maxSum=total[0][0];for(int i=0;i<n;i++)for(int j=i;j<n;j++){int start=0,end=0;for(int k=0;k<n;k++){if(i==0){result[k]=total[j][k];}else{result[k]=total[j][k]-total[i-1][k];}}int sum=getmax(start,end);if(sum>maxSum){maxSum=sum;top=i; bottom=j; left=start; right=end;}}for(int i=top;i<=bottom;i++)for(int j=left;j<=right;j++){cout<<a[i][j];if(j!=right) cout<<" ";else cout<<endl;}cout<<maxSum<<endl;return 0;
}